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