一位小伙伴来问一道谷歌的口试题,对于单链表操作的,问到底有多少种解决方案,明天咱们就来聊聊。
题目的大抵意思是:
假如存在一个无序单链表,将反复结点去除后,并保原程序。去重前:
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 越少~