LC 82: Remove duplicates from the list II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
In other words, remove all elements that have duplicates in the linked list.

We will use a dummy node whose next points to head.

We use two pointers; the slow pointer points to dummyNode and fast pointer points to head. The check for duplicates will be through checking if slow -> next -> val == fast -> next -> val.

slow will always points to unique numbers and we will point its next to the next unique numbers.
If the next is not unique, then we will let fast traverse till fast -> next points to another unique number.
then we will let slow -> next points to it.

If the duplicates exist till the end, eg 1,2,3,3,3,3,3,3, then the while loop where fast progress will stop where fast points to the last duplicate and fast -> next points to null. So we can do the same: just point slow -> next to fast -> next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {

        if(head == NULL)
            return head;

        ListNode dummyHead(-1);
        dummyHead.next = head;
        ListNode* slow = &dummyHead;
        ListNode* fast = dummyHead.next;

        while(fast != NULL && fast -> next != NULL){
            if(slow -> next -> val == fast -> next -> val){
                while(fast -> next != NULL && slow -> next -> val == fast -> next -> val){ //see the same number
                    fast = fast -> next;
                }
                slow -> next = fast-> next;
                fast = fast -> next;
            }
            else{
                slow = slow -> next;
                fast = fast -> next;
            }


        }

        return dummyHead.next;



    }
};

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax