Leecode第83题--删除排序链表中的重复元素

一、问题是什么给一个已经排好序的单链表删掉重复元素让每个值只出现一次。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→1cur在第一个 1跳过第二个 →1→1如果这时前进就漏了所以停在原地再比一次直到cur.next不等于cur才cur cur.next指针变化示意1→1→2textcur ↓ 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三个指针分工指针作用dummy假头永远不动最后return dummy.next拿真头tail新链表尾负责「追加 后移」cur遍历原链表三、核心模板背下来链表追加节点的唯一正确写法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跳过假头假头的val0是占位不是答案。五、复杂度解法时间空间原地删除O(n)O(1)重建新链表O(n)O(n)新节点时间都是 O(n)每个节点最多访问一次。原地版胜在省内存面试一般期待这个重建版胜在不动输入适合「不能修改原链表」的场景。六、一句话总结因为有序重复值必相邻遍历时「相同就跳过原地或忽略重建不同就保留」用dummy tail统一处理头节点时间 O(n)原地版空间 O(1)。个人思路先判断当前的head是否为空然后创建假头和尾指针每一次有val进来尾指针往后移再创建一个head往后移动的指针如果当前head的指针不为空的话比较两个指针现在指向的值一样的话head的指针往后移动不一样的话先把当前head的值写进创建的ListNode中然后将尾指针往后移动最后返回创建指针的后一位。