LeetCode Remove Duplicates from Sorted List I and II: Pointer Manipulation

Overview

The essential idea to solve LeetCode Remove Duplicates from Sorted List I and II problem is to identify the duplicated sub list by keeping two pointers.

LeetCode Remove Duplicates from Sorted List I and II

(1)

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

(2)

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.

Solution Analysis: Use two pointers to identify the duplicated sub list

This problem checks your knowledge about pointers. The first question is much easier, just keep two pointers, one for the current node, one for the next node, if next is the same with the current, then delete the next node, and keep moving on until then end of the list. Return the original head is ok. The following code implements this idea and is accepted by LeetCode OJ to pass this Remove Duplicates from Sorted List I problem:

class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            if (NULL == head || NULL == head->next)
                return head;

            ListNode *p0 = head;
            ListNode *p1 = head->next;

            while (p1) {
                if (p1->val == p0->val) {
                    p0->next = p1->next;
                    p1->next = NULL;
                    delete p1;
                    p1 = p0->next;
                }
                else {
                    p0 = p0->next;
                    p1 = p1->next;
                }
            }
            return head;
        }

};

The second question is much more complicated. First, the head of the new list could be different from the original one. Second, you might need three pointers A, B, C, always keep in mind the nodes between [B, C) are the actual duplicated ones you want to check for duplication, if the length of [B, C) is larger than 1, then delete the whole interval, pointer A always points to the node just before B for the usage of deletion. The tricky part is that for this question, you have to be careful about the NULL pointer details. I just use an additional flag to indicate whether the first non-duplicated node is found or not. This is important because the positions of A, B, C really depends on this fact, and the processing logic is a bit different based on such fact. The following code successfully passed this LeetCode Remove Duplicates from Sorted List II problem:

class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            if (NULL == head || NULL == head->next)
                return head;

            ListNode s(0);
            s.next = head;

            ListNode *t(&s);
            ListNode *p1(head), *p2(head);
            ListNode *h(head);

            while (h && h->next) {
                p1 = p2 = h;
                while (p2->next && p1->val == p2->next->val)
                    p2 = p2->next;
                if (p1 == p2) {
                    h = p2->next;
                    t = p2;
                }
                else {
                    h = t->next = p2->next;
                    p2->next = NULL;
                    while (1) {
                        if (p1 == p2) {
                            delete p1;
                            break;
                        }
                        ListNode *tmp = p1->next;
                        p1->next = NULL;
                        delete p1;
                        p1 = tmp;
                    }
                }
            }
            return s.next;
        }
};

**Open Question: Can we tackle these problems in recursive manner? **

Summary

The essential idea to solve LeetCode Remove Duplicates from Sorted List I and II problem is to identify the duplicated sub list by keeping two pointers.

Written on April 20, 2013