LeetCode Remove Duplicates from Sorted List II

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。

Leave a Reply

Your email address will not be published. Required fields are marked *