Remove Duplicates from Sorted List II

/*
Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

For example,
Given 1->2->3->3->4->4->5, return 1->2->5.
Given 1->1->1->2->3, return 2->3.
*/

#include <set>
#include <string>
#include <iostream>

using namespace std;

//Time O(nlongn), space O(n)
struct node{
    int val;
    node *next;
    node(int v = 0): val(v), next(NULL){}; 
};

class Solution{
public:
    node* RemoveDuplicates(node* n){
        set<int> dup;
        set<int> count;
        node *guard = new node(-1);
        guard->next = n;
        while (NULL != n){//n
            if (count.find(n->val) != count.end()){//logn
                dup.insert(n->val);
            }
            else{
                count.insert(n->val);
            }
            n = n->next;
        }

        n = guard->next;
        node *prev = guard;
        while (NULL != n){
            if (dup.find(n->val) != dup.end()){
                prev->next = n->next;//delete
                delete n;
                n = prev->next;
            }
            else{
                prev = n;
                n = n->next;
            }
        }
        node * re = guard->next;
        delete guard;
        return re;
    }
};

void PrintLinkedList(node *root){
    if (NULL == root) return;
    while (NULL != root->next){
        cout << root->val << "->";
        root = root->next;
    }
    cout << root->val << endl;
}

node * LinkedList(int *a, int l){
    if (0 == l || NULL == a) return NULL;
    node *root = new node(a[0]);
    node *prev = root;
    for (int i = 1; i < l; ++i){
        node *n = new node(a[i]);
        prev->next = n;
        prev = n;
    }
    return root;
}

void DeleteLinkedList(node *root){
    if (NULL == root) return;
    node *next = NULL;
    while (NULL != root){
        next = root->next;
        delete root;
        root = next;
    }
}

int main(){
    Solution sol;
    int a1[] = {1,2,3,4,5,6};
    node * root1 = LinkedList(a1, sizeof(a1)/sizeof(int));
    int a2[] = {1,2,1,4,4,6};
    node * root2 = LinkedList(a2, sizeof(a2)/sizeof(int));
    int a3[] = {3,4,1,4,4,1};
    node * root3 = LinkedList(a3, sizeof(a3)/sizeof(int));

    PrintLinkedList(root1);
    root1 = sol.RemoveDuplicates(root1);
    PrintLinkedList(root1);

    PrintLinkedList(root2);
    root2 = sol.RemoveDuplicates(root2);
    PrintLinkedList(root2);

    PrintLinkedList(root3);
    root3 = sol.RemoveDuplicates(root3);
    PrintLinkedList(root3);

    DeleteLinkedList(root3);
    DeleteLinkedList(root2);
    DeleteLinkedList(root1);
}

ListNode *deleteDuplicates(ListNode *head) {
if(!head||!head->next)return head;
ListNode *p=head->next;
if(head->val==p->val)
{
    while(head->val==p->val)
    {
        p=p->next;
        if(!p)break;
    }
    return deleteDuplicates(p);
}
head->next=deleteDuplicates(head->next);
return head;
}

`public class Solution {

public ListNode deleteDuplicates(ListNode head) {
    // Start typing your Java solution below
    // DO NOT write main() function 
    ListNode re,tail,pre=head,cur=head;       
    re = new ListNode(0);
    tail=re;        
    while(cur!=null&&cur.next!=null){
        while(cur.next!=null&&cur.val==cur.next.val) cur=cur.next;
        if(pre==cur){  //distinct value                
            tail.next=pre;
            tail=tail.next;
        }                                         
        pre=cur.next;
        cur=cur.next;          
    }
    tail.next=cur; //add the last value
    return re.next; //dump the dummy node
}

}`

ListNode *deleteDuplicates(ListNode *head) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function

    // base case, 0, or 1 item in the list
    if (head == NULL || head->next == NULL) return head;        
    ListNode *ret=NULL;
    ListNode *cur = head;
    int dup=0;

    // remove duplicated values from head
    while (cur->next != NULL && cur->val == cur->next->val)
    {
        ListNode *t=cur;
        cur=cur->next;
        delete(t);
        dup = 1;
    }

    if (!dup)
    {
        ret = cur;
        cur->next = deleteDuplicates(cur->next);            
    }
    else
    {
        ret = deleteDuplicates(cur->next);
    }    
    return ret;        
}

class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode dummy(0);
        dummy.next = head;

        ListNode *pre = &dummy, *cur = head;
        while (cur) {
            int i = cur->val;
            if (cur->next && cur->next->val == i) {
                while (cur && cur->val == i) {
                    pre->next = cur->next;
                    delete cur;
                    cur = pre->next;
                }
                cur = pre;
            }
            pre = cur;
            cur = cur->next;
        }

        return dummy.next;
    }
};

public ListNode deleteDuplicates(ListNode head) {
    if (head == null) return null;

    ListNode root = new ListNode(-1);
    ListNode root_last = root, cur_node = head;
    while (cur_node != null) {
        ListNode next_node = cur_node.next;
        boolean found_dup = false;
        while (next_node != null && next_node.val == cur_node.val) {
            found_dup = true;               
            next_node = next_node.next;
        }
        if (found_dup) {
            // skip cur_node, directly to next_node
            cur_node = next_node;
        } else {
            root_last.next = cur_node;
            root_last = cur_node;
            root_last.next = null;// clear the original next
            cur_node = next_node;
        }
    }
    return root.next;
}

public class Solution {
public ListNode deleteDuplicates(ListNode head) {
    // Start typing your Java solution below
    // DO NOT write main() function
    if (head==null) return head;
    ListNode curr = head.next;
    ListNode prev = head;
    ListNode keep = null;
    while (curr != null) {
        while (curr != null && curr.val == prev.val) {
            curr = curr.next;
        }
        if (curr == null) {
            if (keep == null) return null;
            keep.next = null;
            return head;
        }
        if (prev.next == curr) {
            if (keep != null) 
                keep.next = prev;
            else 
                head = prev;
            keep = prev;
        }
        prev = curr;
        curr = curr.next;
    }
    if (prev.next == curr) {
        if (keep == null) {
            keep = head = prev;
        } else {
            keep.next = prev;
        }
    }
    return head;
}
}

Use 3 pointers pv, hd, nx to point to previous node, current node, and next node.

ListNode *deleteDuplicates(ListNode *head) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (!head || !head->next) {
        return head;
    }

    bool found_equ = false;
    ListNode *pv, *hd, *nx;
    pv = NULL;
    hd = head;
    nx = hd->next;

    for (; nx != NULL; nx = nx->next) {
        if (hd->val == nx->val) {
            found_equ = true;
            hd->next = nx->next;
        } else {
            if (found_equ) {
                if (pv) {
                    pv->next = hd->next;
                }
                found_equ = false;
            } else {
                if (!pv) {
                    pv = hd;
                    head = pv;
                }
                else
                    pv = pv->next;
            }
            hd = hd->next;
        }
    }

    if (found_equ) {
        if (!pv) {
            pv = hd->next;
            head = pv;
        }
        else {
            pv->next = hd->next;
        }
    } else {
        if (!pv) {
            pv = hd;
            head = pv;
        }
    }

    return head;
}

ListNode *deleteDuplicates(ListNode *head) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    ListNode *cur = head; // current pointer
    ListNode *prv = head; // previous pointer
    while (cur) {
        if (!cur->next) {
            break;
        }
        if (cur->val != cur->next->val) {
            prv = cur;
            cur = cur->next;
        }
        else {
            ListNode *cur_tmp = cur;
            while (cur->val == cur->next->val) {
                cur = cur->next;
                if (cur->next == NULL) {
                    break;
                }
            }
            cur = cur->next;
            prv->next = cur;
            if (cur_tmp == prv) {
                prv = cur;
                head = prv;
            }
        }
    }
    return head;
}

recursive solution /* * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } / public class Solution { public ListNode deleteDuplicates(ListNode head) { // Start typing your Java solution below // DO NOT write main() function

    if(head == null){
        return head;
    }
    boolean hasDuplicate = false;

    while(head.next!= null && head.next.val == head.val){
        head = head.next;
        hasDuplicate = true;
    }
    if(hasDuplicate){
        head=deleteDuplicates(head.next);
    }
    else{
        head.next=deleteDuplicates(head.next);
    }
    return head;
}

}