82. Remove Duplicates from Sorted List II

Description

Given the head of 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: head = [1,2,3,3,4,4,5]
Output: [1,2,5]

Example 2:

Input: head = [1,1,1,2,3]
Output: [2,3]

Constraints:

• The number of nodes in the list is in the range [0, 300].
• 100 <= Node.val <= 100
• The list is guaranteed to be sorted in ascending order.

---

解题

方法一

思路

快慢指针，

1. 遇到相同的快指针（curr）不断往后移
2. 慢指针（prev）发现自己后面指的节点不是当初的那个节点（说明有重复节点，需要删除），直接把链接连到快指针后面，如果还是当初连的那个快节点的话，就保留当前节点，再进一步
3. 快指针往后继续移

代码

public ListNode deleteDuplicates(ListNode head) {
    ListNode dummy = new ListNode(0);
    ListNode prev = dummy, curr = head;
    prev.next = head;
    while (curr != null) {
        while (curr.next != null && curr.val == curr.next.val) {
            curr = curr.next;
        }
        if (prev.next != curr) {
            prev.next = curr.next;
        } else {
            prev = prev.next;
        }
        curr = curr.next;
    }
    return dummy.next;
}

---

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *prev = dummy;
        while (prev->next) {
            ListNode *curr = prev->next->next;
            while (curr && prev->next->val == curr->val) {
                curr = curr->next;
            }
            if (prev->next->next == curr) {
                prev = prev->next;
            } else {
                prev->next = curr;
            }
        }
        return dummy->next;
    }
};

复杂度分析

• 时间复杂度: O(n)
• 空间复杂度: O(1)