82. 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.
Return the linked list sorted as well.
Example 1:
Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:
Input: 1->1->1->2->3
Output: 2->3
把已排序链表中有重复元素的节点删掉，只保留出现一次的节点，看样例就可以知道这是怎么回事了。 此题有两个步骤，第一是找到新的头结点，第二是删掉后续的重复节点。 找新头结点时，维护一个head和tail指针，如果tail的val和head的val相同，则更新head和tail， 直到tail为空或者遇到一个distinct的head。 删掉后续重复节点时，维护一个sub_head、prior和tail，如果prior和tail的val相同，则把所有相同的节点都删掉，方法是直接把sub_head的next指向所有相同元素的下一个元素，同时更新prior和tail。 完整代码如下：
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode* tail = head->next;
while (tail != NULL) { // find new head
int cnt = 0;
while (tail != NULL && tail->val == head->val) {
tail = tail->next;
cnt++;
}
if (tail == NULL)
return NULL;
if (cnt == 0)
break;
else {
head = tail;
tail = head->next;
}
}
ListNode *sub_head = head, *prior = sub_head->next;
while (prior != NULL) { // delete all duplicate nodes
tail = prior->next;
int cnt = 0;
while (tail != NULL && tail->val == prior->val) {
tail = tail->next;
cnt++;
}
//if (tail == NULL)break;
if (cnt == 0) {
sub_head = prior;
prior = prior->next;
}
else {
sub_head->next = tail;
prior = tail;
}
}
return head;
}
};
本代码提交AC，用时9MS。
二刷。完全不记得一刷的解法了。二刷参考https://discuss.leetcode.com/topic/29849/c-8ms-iterative-naive-but-easy-to-implement，很好理解的一个方法。
设置一个标签to_be_added，为true表明这个节点unique，需要添加到结果链表中，否则重复，需要删除。直接判断head和head->next的值是否相等，如果相等，则需要把所有等于head的节点删掉，比如说样例[1,1,1,2,3]，head=1,head->next=1，相等，则把head删掉；接着，head到了第二个1，发现等于第三个1，所以把第二个1删掉；接着head走到第三个1，此时head->next->val != head-val，跳出循环，但是因为to_be_added=false，说明1这个数重复了，所以还是需要把head删掉。只有to_be_added=true才会加入到结果链表中。
最后记得把tail->next=NULL置空，并且所有该删除的节点真的要delete掉。
完整代码如下：
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head)
{
if (head == NULL || head->next == NULL)
return head;
ListNode* dummy = new ListNode(0 == head->val ? 1 : 0);
ListNode *tail = dummy, *delete_node;
bool to_be_added = true;
while (head) {
while (head->next && head->val == head->next->val) {
delete_node = head;
head = head->next;
delete delete_node;
to_be_added = false;
}
if (to_be_added) {
tail->next = head;
tail = tail->next;
head = head->next;
}
else {
delete_node = head;
head = head->next;
delete delete_node;
}
to_be_added = true; // reset
}
tail->next = NULL;
delete_node = dummy;
dummy = dummy->next;
delete delete_node;
return dummy;
}
};
本代码提交AC，用时6MS。
三刷。简洁版代码，新建一个链表，把原链表中没有重复值的节点接到新链表中，代码如下：
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL)return head;
ListNode *new_head = new ListNode(0);
ListNode *l0=new_head, *l1 = head, *l2 = head->next;
while (l2) {
l2 = l1->next;
int count = 0;
while (l2 != NULL && l2->val == l1->val) {
l2 = l2->next;
++count;
}
if (count == 0) {
l0->next = l1;
l0 = l0->next;
}
l1 = l2;
}
l0->next = NULL;
return new_head->next;
}
};
本代码提交AC，用时12MS。