Remove duplicates from list

Almost the same as the first one, but this time we will simply delete duplicates such that each number only appear once.

After the while loop, we will just move slow forward once so it points to the first of many( >= 2) duplicates and points slow -> next to the next unique number.

/**
 * 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) {
        ListNode* fast;
        ListNode* slow;
        ListNode dummyNode(-1);
        dummyNode.next = head;
        slow = &dummyNode;
        fast = head;

        while(fast && fast -> next != NULL){
            if(fast -> next -> val == slow -> next -> val ){
                while(fast -> next && fast -> next -> val == slow -> next -> val){
                    fast = fast -> next;
                }
                slow = slow -> next;
                slow -> next = fast -> next;
                fast = fast -> next;

            }
            else{
                fast = fast ->next;
                slow = slow -> next;

            }
        }
     return dummyNode.next;   
    }
};

A simpler method

We will just use one pointer

/**
 * 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) {
        ListNode* curr = head;
        while(curr && curr -> next){
            if(curr ->next ->val == curr ->val){
                curr -> next = curr->next->next;
            }
            else
                curr = curr->next;
        }
        return head;
    }

};

Recursive

We use a helper function that will iterate through the linked list and will skip duplicates.

/**
 * 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) {
        recurHelper(head);
        return head;
    }

    void recurHelper(ListNode* head){
        if(!head || !head -> next)
            return;
        while(head -> val == head -> next ->val){
            head -> next = head -> next -> next;
            if(!head -> next)return;
        }
        recurHelper(head -> 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