2014
11-19

# LeetCode-Remove Duplicates from Sorted List II[链表]

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

// LeetCode, Remove Duplicates from Sorted List II
// 递归版，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {

ListNode *p = head->next;
if (head->val == p->val) {
while (p && head->val == p->val) {
ListNode *tmp = p;
p = p->next;
delete tmp;
}
return deleteDuplicates(p);
} else {
}
}
};


// LeetCode, Remove Duplicates from Sorted List II
// 迭代版，时间复杂度O(n)，空间复杂度O(1)
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {

ListNode dummy(INT_MIN); // 头结点
ListNode *prev = &dummy, *cur = head;
while (cur != nullptr) {
bool duplicated = false;
while (cur->next != nullptr && cur->val == cur->next->val) {
duplicated = true;
ListNode *temp = cur;
cur = cur->next;
delete temp;
}
if (duplicated) { // 删除重复的最后一个元素
ListNode *temp = cur;
cur = cur->next;
delete temp;
continue;
}
prev->next = cur;
prev = prev->next;
cur = cur->next;
}
prev->next = cur;
return dummy.next;
}
};