[LeetCode] Remove Duplicates from Sorted List I && II

Remove Duplicates from Sorted List I

Problem Statement (link):

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.

Analysis:
Use two pointers, one pointer points to the current node, the other pointer advances if there's duplicates.

The time complexity is O(n), where n is length of the linked list. The space complexity is constant.

Code:

/**
 * 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) {
        if (head==NULL || head->next==NULL) return head;

        ListNode *p1=head;
        while (p1->next!=NULL) {
            ListNode *p2=p1->next;
            while (p2 && p1->val==p2->val)
                p2=p2->next;

            if (p1->next==p2) // no dup
                p1=p1->next;
            else
                p1->next=p2;
        }
        return head;
    }
};

Remove Duplicates from Sorted List II

Problem Statement (link):

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.

Analysis:
Once the previous problem is understood, the only difference with this problem is that we need to save previous node.

Code:

/**
 * 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) {
        if (head==NULL || head->next==NULL) return head;

        ListNode *prev=new ListNode(INT_MIN);
        prev->next=head;
        head=prev;
        while(prev->next!=NULL) {
            ListNode *curr=prev->next;
            // advance pointer if duplicate
            while(curr->next && curr->val==curr->next->val)
                curr=curr->next;

            if (curr!=prev->next) // re-link prev if duplicate
                prev->next=curr->next;
            else    // advance prev if no duplicate
                prev=prev->next;
        }
        return head->next;
    }
};