【数据结构基础_链表】Leetcode 82.删除排序链表中的重复元素II

原题连接：Leetcode 82. Remove Duplicates from Sorted List II

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]
1
2

Example 2:

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

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.

---

方法一：迭代_一次遍历

思路：

首先链表是有序的
那么重复的元素一定就在一起，设置两个指针：

• pre：指向已经完成删除的部分的结尾
• cur：用于跳过存在重复结点的区间（也就是删除）

因为头结点也有可能删除，添加一个虚拟头结点

举个例子： 以 112334 为例

c++代码：

/**
 * 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) {
        // 提前返回的情况
        if (!head || !head->next) 
            return head;

        // 虚拟头结点
        ListNode* preHead = new ListNode(0);
        preHead->next = head;
        
        // 两个指针，用于找到重复元素的区间
        ListNode* pre = preHead;
        ListNode* cur = head;

        while (cur) {
            // 如果cur处于重复元素区间中，则将cur移动到当前重复元素所在区间的最后一个结点
            while (cur->next && cur->val == cur->next->val) {
                cur = cur->next;
            }
            // pre和cur之间没有重复节点，pre后移
            if (pre->next == cur) {
                pre = pre->next; 
            } 
            // 之间隔着重复结点区间
            else {
            	// 跳过重复元素的区间
                pre->next = cur->next;
            }
            cur = cur->next;
        }
        return preHead->next;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

复杂度分析：

• 时间复杂度：O(n)，遍历一遍链表
• 空间复杂度：O(1)，常数个临时变量