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.

Problem link

Solution

  • The original head could be removed, therefore introduce dummy head to simplify the program
  • be careful about the case where reading the end and still need to delete elements
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode* dummy = new ListNode(0);
        if (!head) return NULL;
        dummy->next = head;
        ListNode* pre = dummy;
        int same = false;
        while (head->next){
            if (head->val == head->next->val){
                same = true;
            }else{ // not equal for now
                if (same == true){
                    pre->next = head->next; // delete
                    same = false;
                }else{
                    pre = head;
                }
            }
            head = head->next;
        }
        if (same == true){
            pre->next = head->next;
        }
        head = dummy->next;
        delete dummy;
        return head;
    }
};
Advertisements
Remove Duplicates from Sorted List II

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s