企业官网建设流程全解析

一、问题是什么

给一个已经排好序的单链表，删掉重复元素，让每个值只出现一次。

text

输入：1 → 1 → 2 → 3 → 3 输出：1 → 2 → 3

关键前提：链表有序。这意味着相同的值一定挨在一起，不用哈希表记录「出现过没有」，只要和相邻的比较就行。这是整个算法能 O(n)、O(1) 的根本原因。

二、两种解法

这道题有两条路，取决于「能不能改原链表」：

解法 1：原地删除（推荐，O(1) 空间）

不改值、不建新节点，只改指针，把重复节点「跳过」。

class Solution: def deleteDuplicates(self, head: ListNode | None) -> ListNode | None: cur = head while cur and cur.next: if cur.val == cur.next.val: cur.next = cur.next.next # 跳过重复节点 else: cur = cur.next # 不重复才前进 return head

为什么重复时不前进？因为可能连续三个相同1→1→1：

• cur在第一个 1，跳过第二个 →1→1

• 如果这时前进，就漏了；所以停在原地再比一次

• 直到cur.next不等于cur，才cur = cur.next

指针变化示意（1→1→2）：

text

cur ↓ 1 → 1 → 2 ↑ cur.next 相同，跳过 cur ↓ 1 ────→ 2 ↑ cur.next 不同，cur 前进

解法 2：重建新链表（你一直在写的，O(n) 空间）

不改原链表，新建一条只含去重值的链表。

class Solution: def deleteDuplicates(self, head: ListNode | None) -> ListNode | None: dummy = ListNode(0) tail = dummy cur = head while cur: if cur.val != tail.val: tail.next = ListNode(cur.val) tail = tail.next cur = cur.next return dummy.next

三个指针分工：

三、核心模板（背下来）

链表追加节点的唯一正确写法：

tail.next = ListNode(x) # 接在尾部（新建节点） tail = tail.next # 尾指针后移

重建链表的通用骨架：

dummy = ListNode(0) tail = dummy cur = head while cur: if <条件>: tail.next = ListNode(cur.val) tail = tail.next cur = cur.next return dummy.next

这个骨架能套用到很多题：合并两个有序链表、分隔链表、删除节点、反转链表的重建版……换的只是<条件>和「怎么接」。

四、为什么用 dummy（假头）

链表最麻烦的是头节点没有前驱，插入/删除头时要特判。造个dummy当「头的前一个」，所有节点就都有前驱了，逻辑统一，不用if head is None之外的特判。

代价：最后要return dummy.next跳过假头（假头的val=0是占位，不是答案）。

五、复杂度

时间都是 O(n)：每个节点最多访问一次。原地版胜在省内存，面试一般期待这个；重建版胜在不动输入，适合「不能修改原链表」的场景。

六、一句话总结

因为有序，重复值必相邻；遍历时「相同就跳过（原地）或忽略（重建），不同就保留」，用dummy + tail统一处理头节点，时间 O(n)，原地版空间 O(1)。

个人思路：

先判断当前的head是否为空，然后创建假头和尾指针，每一次有val进来尾指针往后移，再创建一个head往后移动的指针，如果当前head的指针不为空的话，比较两个指针现在指向的值，一样的话head的指针往后移动，不一样的话先把当前head的值写进创建的ListNode中，然后将尾指针往后移动，最后返回创建指针的后一位。