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.

/**
 * 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) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    if (head == NULL || head->next == NULL)
        return head;
    ListNode *front = head;
    ListNode *back = NULL;
    while (front != NULL)
    {
        //find the first duplicating node
        while (front->next != NULL && front->next->val != front->val)
        {
            back = front;
            front = front->next;
        }
        if (front->next == NULL) //we have arrived at the last node in the list, done searching
            return head;
        else //now front points at the beginning of the duplicating nodes
        {
            //find the end of the duplicating nodes
            while (front->next != NULL && front->next->val == front->val)
                front = front->next;
            //now front is at the end of the duplicating nodes
            ListNode *nextNode = front->next;
            if (back == NULL) //duplicates start at the beginning of the linked list
                head = nextNode; //back stays NULL, update the head pointer
            else
                back->next = nextNode;
            //update front node
            front = nextNode;
        }//endelse
        //printList(L);
    }//endwhile
    return head;
}
};
This entry was posted in LeetCode and tagged , . Bookmark the permalink.

Leave a comment