删除链表中重复的节点

发表于 更新于 分类于 本文字数： 433 阅读时长 ≈ 2 分钟

JZ76 删除链表中重复的结点

描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

例如，链表 $1\rightarrow 2\rightarrow 3\rightarrow 3\rightarrow 4\rightarrow 4\rightarrow 5$ 处理后为 $1\rightarrow 2\rightarrow 5$

数据范围：链表长度满足$0≤n≤1000$，链表中的值满足 $1≤val≤1000$

进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(n)$

例如输入{1,2,3,3,4,4,5}时，对应的输出为{1,2,5}，对应的输入输出链表如下图所示：
img

示例1

1
2
输入：{1,2,3,3,4,4,5}
返回值：{1,2,5}

示例2

1
2
输入：{1,1,1,8}
返回值：{8}

题解

关键点：链表是排序了的，要删除重复了的全部结点（不需要保留）

思路：三指针，$prev,curr,future$，$prev$保留前一个，当$curr$与$future$相同时，$future$不断前进直到二者不同$prev\rightarrow next = future$,$prev$进一步，重置$curr = prev\rightarrow next,future = curr\rightarrow next$。

思路基本上是对的，在写的时候因为考虑到前两个元素重复的情况，所以没有用$prev$，后续也证明确实我这样反而写复杂了，问了下GPT，学到了一手在链表头再插一个独特元素(本题中使用0即可，可参考$val$的取值范围)。

代码

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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (!pHead) return nullptr;

        ListNode dummy(0);
        dummy.next = pHead;
        ListNode* prev = &dummy;
        ListNode* curr = pHead;

        while (curr) {
            bool duplicated = false;
            // 找到一段重复区间
            while (curr->next && curr->val == curr->next->val) {
                duplicated = true;
                curr = curr->next;
            }

            if (duplicated) {
                // 跳过整段重复节点
                prev->next = curr->next;
            } else {
                // 保留当前节点，prev 往前走
                prev = curr;
            }
            curr = curr->next;
        }

        return dummy.next;
    }
};