## 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.

 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; } };

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:

1. if(pre->next!=cur) 來取代 var duplicate 不好嗎