Wednesday, November 19, 2014

[LeetCode] Remove Duplicates from Sorted List I, II

Remove Duplicates from Sorted List I

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.

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.

思路:Remove Duplicates from Sorted List I

由于list已经排序过,重复节点必相邻。由于链表指针是单向的,所以访问每个节点时,判断后一个节点是否是重复节点,如果是,则删除后一个节点。由于I中重复节点要保留一个,如果碰到重复删除后节点,则不需要考虑删除头指针的特殊情况。


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        if(!head) return head;
        ListNode *cur = head;
        while(cur->next) {
            if(cur->val == cur->next->val) {
                ListNode *temp = cur->next;
                cur->next = temp->next;
                delete temp;
            }
            else {
                cur = cur->next;
            }
        }
        return head;        
    }
};


思路:Remove Duplicates from Sorted List II

II比I难在需要删除所有的重复节点。这里需要注意两点:
1. 头节点也可能被删除。可以使用dummy节点来简化。
2. 如果采用与I类似的思路来删除当前节点后所有的重复节点,则完成后还需要把当前节点也删除。因此需要有一个变量来记录当前节点是否有重复。



 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *dummy = new ListNode(0);
        dummy->next = head;
        ListNode *pre = dummy, *cur = head;
        bool duplicate = false;
        
        while(cur) {
            if(cur->next && cur->val==cur->next->val) {
                ListNode *temp = cur->next;
                cur->next = temp->next;
                delete temp;
                duplicate = true;
            }
            else if(duplicate) {
                pre->next = cur->next;
                delete cur;
                cur = pre->next;
                duplicate = false;
            }
            else {
                pre = cur;
                cur = cur->next;
            }
        }
        
        head = dummy->next;
        delete dummy;
        return head;
    }
};

1 comment: