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。