谷歌面试题：如何从无序链表中移除重复项？

雨点打透心脏的1/2处 2022-11-01 00:52 92阅读 0赞

一位小伙伴来问一道谷歌的笔试题，关于单链表操作的，问到底有多少种解决方案，今天我们就来聊聊。

题目的大致意思是：

假设存在一个无序单链表，将重复结点去除后，并保原顺序。去重前：1→3→1→5→5→7去重后：1→3→5→7

顺序删除

通过双重循环直接在链表上执行删除操作。外层循环用一个指针从第一个结点开始遍历整个链表，然后内层循环用另外一个指针遍历其余结点，将与外层循环遍历到的指针所指结点的数据域相同的结点删除，如下图所示。

假设外层循环从outerCur开始遍历，当内层循环指针innerCur遍历到上图实线所示的位置（outerCur.data==innerCur.data）时，此时需要把innerCur指向的结点删除。

具体步骤如下：

用tmp记录待删除的结点的地址。

为了能够在删除tmp结点后继续遍历链表中其余的结点，使innerCur指针指向它的后继结点：innerCur=innerCur.next。

从链表中删除tmp结点。

实现代码如下：

运行结果：

算法性能分析

由于这种方法采用双重循环对链表进行遍历，因此，时间复杂度为O（N^2）。其中，N为链表的长度。在遍历链表的过程中，使用了常量个额外的指针变量来保存当前遍历的结点、前驱结点和被删除的结点，因此，空间复杂度为O（1）。

递归法

主要思路为：对于结点cur，首先递归地删除以cur.next为首的子链表中重复的结点，接着从以cur.next为首的子链表中找出与cur有着相同数据域的结点并删除。

实现代码如下：

算法性能分析

这种方法与方法一类似，从本质上而言，由于这种方法需要对链表进行双重遍历，因此，时间复杂度为O（N^2）。其中，N为链表的长度。由于递归法会增加许多额外的函数调用，因此，从理论上讲，该方法效率比前面的方法低。

空间换时间

通常情况下，为了降低时间复杂度，往往在条件允许的情况下，通过使用辅助空间实现。

具体而言，主要思路如下。

建立一个HashSet，HashSet中的内容为已经遍历过的结点内容，并将其初始化为空。

从头开始遍历链表中的所以结点，存在以下两种可能性：

如果结点内容已经在HashSet中，则删除此结点，继续向后遍历。

如果结点内容不在HashSet中，则保留此结点，将此结点内容添加到HashSet中，继续向后遍历。

「引申：如何从有序链表中移除重复项？」

如链表：1,3、5、5、7、7、8、9

去重后：1,3、5、7、8、9

分析与解答

上述介绍的方法也适用于链表有序的情况，但是由于以上方法没有充分利用到链表有序这个条件，因此，算法的性能肯定不是最优的。本题中，由于链表具有有序性，因此，不需要对链表进行两次遍历。所以，有如下思路：用cur 指向链表第一个结点，此时需要分为以下两种情况讨论。

如果cur.data==cur.next.data，那么删除cur.next结点。

如果cur.data!=cur.next.data，那么cur=cur.next，继续遍历其余结点。

总结

对于无序单链表中，想要删除其中重复的结点（多个重复结点保留一个）。删除办法有按照顺序删除、使用递归方式删除以及可以使用空间换时间（HashSet中元素的唯一性）。

点赞越多，bug越少~

发表评论取消回复

表情：

评论列表（有 0 条评论，92人围观）

还没有评论，来说两句吧...

相关阅读

相关从数组中移除重复元素

从数组中移除重复元素 const removeDuplicateItems = arr => [...new Set(arr)]; remove

偏执的太偏执、/ 2023年10月09日 12:09/ 0 赞/ 46 阅读

相关链表刷题之移除链表元素

2. 移除链表元素 2.1 LC203 [203. 移除链表元素][203.] 给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满

绝地灬酷狼/ 2023年09月30日 21:53/ 0 赞/ 19 阅读

相关面试题 02.01. 移除重复节点

题目来源 [面试题 02.01. 移除重复节点][02.01.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGV

怼烎@/ 2023年02月20日 07:20/ 0 赞/ 60 阅读

相关大厂面试算法系列-如何从无序链表中移除重复项(二)-递归法

> 导语 > 这种方法主要的思路是对节点cur来说首先递归的删除以cur.next为首的子链表中的重复节点。这个就是递归的主要思想。对于节点cur，首先递归地删

「爱情、让人受尽委屈。」/ 2023年01月15日 14:24/ 0 赞/ 94 阅读

相关谷歌面试题：如何从无序链表中移除重复项？有几种方式？

![format_png][] [点击获取「一份贴心的10万字面试小抄」][10] 一位小伙伴来问一道谷歌的笔试题，关于单链表操作的，问到底有多少种解决方案，今天我们就来聊

Love The Way You Lie/ 2023年01月11日 04:59/ 0 赞/ 71 阅读

相关【力扣】移除重复节点(链表+set)

题目编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。 > 示例1: > > 输入：\[1, 2, 3, 3, 2, 1\] 输出：\[1, 2, 3\]

迈不过友情╰/ 2023年01月11日 01:22/ 0 赞/ 137 阅读

相关大厂面试算法系列-如何从无序链表中移除重复项(一)-顺序删除

> 导语 > 题目描述：给定一个没有经过排序的链表，去掉其中的重复项，并且保留原顺序，例如链表1->2->1->5->5-7,去掉其中的重复项之后会变成 1->2->5

川长思鸟来/ 2023年01月01日 15:54/ 0 赞/ 123 阅读

相关面试题 02.01. 移除重复节点

[面试题 02.01. 移除重复节点][02.01.] [https://leetcode-cn.com/problems/remove-duplicate-node-lcc

朴灿烈づ我的快乐病毒、/ 2022年11月26日 01:51/ 0 赞/ 173 阅读

相关谷歌面试题：如何从无序链表中移除重复项？

一位小伙伴来问一道谷歌的笔试题，关于单链表操作的，问到底有多少种解决方案，今天我们就来聊聊。题目的大致意思是：假设存在一个无序单链表，将重复结点去除后，并保原顺序。去重

雨点打透心脏的1/2处/ 2022年11月01日 00:52/ 0 赞/ 93 阅读

相关移除链表元素

题目描述删除链表中等于给定值 val 的所有节点。示例: 输入: 1->2->6->3->4->5->6, val = 6 输出: 1->2->3

野性酷女/ 2021年12月15日 05:15/ 0 赞/ 252 阅读