【剑指 の 精选】详解「删除链表中重复结点」的两种解法（剑指诸天）

【剑指 の 精选】详解「删除链表中重复结点」的两种解法（剑指诸天）

题目描述

这是「牛客网」上的「JZ 56 删除链表中重复的结点」，难度为「较难」 。

Tag : 「剑指 Offer」、「链表」、「单链表」

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

例如，链表 ​​1->2->3->3->4->4->5​​​ 处理后为 ​​1->2->5​​

示例 1：

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

要求：

时间：1 s空间：64 M

迭代解法

首先一个比较「直观且通用」的思路是，采用「边遍历边构造」的方式：

建一个「虚拟头节点」​​dummy​​ 以减少边界判断，往后的答案链表会接在 ​​dummy​​ 后面；使用 ​​tail​​ 代表当前有效链表的结尾；通过原输入的 ​​pHead​​ 指针进行链表扫描。

对原链表进行遍历，只要原链表尚未到达结尾，我们就重复如下决策（保留/跳过逻辑）：

保留：​​pHead​​ 已经没有下一个节点，​​pHead​​ 可以被保留（插入到答案结尾指针 ​​tail​​ 后面）；​​pHead​​ 有一下个节点，但是值与 ​​pHead​​ 不相同，​​pHead​​ 可以被保留；跳过：当发现 ​​pHead​​ 与下一个节点值相同，需要对「连续相同一段」进行跳过。

举个 ????，以题目示例 ​​[1,2,3,3,4,4,5]​​ 为例，使用图解的方式来感受一下。

「当前节点」与「下一节点」值不同，当前节点进行保留：

「当前节点」与「下一节点」值相同，跳过「相同的连续一段」，当前节点不能保留：

Java 代码：

class Solution { public ListNode deleteDuplication(ListNode pHead) { ListNode dummy = new ListNode(-1); ListNode tail = dummy; while (pHead != null) { // 进入循环时，确保了 pHead 不会与上一节点相同 if (pHead.next == null || pHead.next.val != pHead.val) { tail.next = pHead; tail = pHead; } // 如果 pHead 与下一节点相同，跳过相同节点（到达「连续相同一段」的最后一位） while (pHead.next != null && pHead.val == pHead.next.val) pHead = pHead.next; pHead = pHead.next; } tail.next = null; return dummy.next; }}

Python 3 代码：

class Solution: def deleteDuplication(self, pHead): dummy = ListNode(-1) tail = dummy while pHead is not None: # 进入循环时，确保了 pHead 不会与上一节点相同 if pHead.next is None or pHead.next.val != pHead.val: tail.next = pHead tail = pHead # 如果 pHead 与下一节点相同，跳过相同节点（到达「连续相同一段」的最后一位） while pHead.next is not None and pHead.val == pHead.next.val: pHead = pHead.next pHead = pHead.next tail.next = None return dummy.next

时间复杂度：O(n)空间复杂度：O(n)

递归解法

递归解法相比于迭代解法，代码要简洁一些，但思维难度要高一些。

首先无论是否为“链表”类的题目，在实现递归前，都需要先明确「我们期望递归函数完成什么功能」，即设计好我们的递归函数签名。

显然，我们希望存在一个递归函数：传入链表头结点，对传入链表的重复元素进行删除，返回操作后的链表头结点。

该功能与题目要我们实现的 ​​deleteDuplication​​ 函数相同，因此我们直接使用原函数作为递归函数即可。

之后再考虑「递归出口」和「递归环节的最小操作」：

递归出口：考虑什么情况下，我们不再需要「删除」操作。显然当传入的参数 ​​pHead​​ 为空，或者 ​​pHead.next​​ 为空时，必然不存在重复元素，可直接返回 ​​pHead​​；递归环节的最小操作：之后再考虑删除逻辑该如何进行：显然，当 ​​pHead.val != pHead.next.val​​  时，​​pHead​​ 是可以被保留的，因此我们只需要将 ​​pHead.next​​ 传入递归函数，并将返回值作为 ​​pHead.next​​，然后返回 ​​pHead​​ 即可；当 ​​pHead.val == pHead.next.val​​ 时，​​pHead​​ 不能被保留，我们需要使用临时变量 ​​tmp​​ 跳过「与 ​​pHead.val​​ 值相同的连续一段」，将 ​​tmp​​ 传入递归函数所得的结果作为本次返回。

Java 代码：

public class Solution { public ListNode deleteDuplication(ListNode pHead) { // 递归出口：当「输入节点为空」或者「不存在下一节点」，直接返回 if (pHead == null || pHead.next == null) return pHead; if (pHead.val != pHead.next.val) { // 若「当前节点」与「下一节点」值不同，则当前节点可以被保留 pHead.next = deleteDuplication(pHead.next); return pHead; } else { // 若「当前节点」与「下一节点」相同，需要跳过「值相同的连续一段」 ListNode tmp = pHead; while (tmp != null && tmp.val == pHead.val) tmp = tmp.next; return deleteDuplication(tmp); } }}

Python 3 代码：

class Solution: def deleteDuplication(self, pHead): # 递归出口：当「输入节点为空」或者「不存在下一节点」，直接返回 if pHead is None or pHead.next is None: return pHead if pHead.val != pHead.next.val: # 若「当前节点」与「下一节点」值不同，则当前节点可以被保留 pHead.next = self.deleteDuplication(pHead.next) return pHead else: # 若「当前节点」与「下一节点」相同，需要跳过「值相同的连续一段」 tmp = pHead while tmp is not None and tmp.val == pHead.val: tmp = tmp.next return self.deleteDuplication(tmp)

时间复杂度：O(n)空间复杂度：忽略递归带来的额外空间开销，复杂度为 O(1)

拓展

如果问题变为「相同节点保留一个」，该如何实现？

本质没有改变，只需要抓住「遍历过程中，节点何时能够被保留」即可。

Java 代码：

class Solution { public ListNode deleteDuplication(ListNode head) { if (head == null) return head; ListNode dummy = new ListNode(-109); ListNode tail = dummy; while (head != null) { // 值不相等才追加，确保了相同的节点只有第一个会被添加到答案 if (tail.val != head.val) { tail.next = head; tail = tail.next; } head = head.next; } tail.next = null; return dummy.next; } }

Python 3 代码：

class Solution: def deleteDuplication(self, pHead): if pHead is None: return pHead dummy = ListNode(-109) tail = dummy while pHead is not None: # 值不相等才追加，确保了相同的节点只有第一个会被添加到答案 if tail.val != pHead.val: tail.next = pHead tail = tail.next pHead = pHead.next tail.next = None return dummy.next

时间复杂度：空间复杂度：

最后

这是我们「剑指 の 精选」系列文章的第 ​​No.56​​ 篇，系列开始于 2021/07/01。

该系列会将「剑指 Offer」中比较经典而又不过时的题目都讲一遍。

在提供追求「证明」&「思路」的同时，提供最为简洁的代码。

欢迎关注，交个朋友 (｀・ω・´)

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。