Find duplicates in linked list Python

Question

Write a removeDuplicates[] function which takes a list and deletes any duplicate nodes from the list. The list is not sorted. For example if the linked list is 12->11->12->21->41->43->21, then removeDuplicates[] should convert the list to 12->11->21->41->43. If temporary buffer is not allowed, how to solve it?

题解1 - 两重循环

Remove Duplicates 系列题，之前都是已排序链表，这个题为未排序链表。原题出自 CTCI 题2.1。

最容易想到的简单办法就是两重循环删除重复节点了，当前遍历节点作为第一重循环，当前节点的下一节点作为第二重循环。

Python

""" Definition of ListNode class ListNode[object]: def __init__[self, val, next=None]: self.val = val self.next = next """ class Solution: """ @param head: A ListNode @return: A ListNode """ def deleteDuplicates[self, head]: if head is None: return None curr = head while curr is not None: inner = curr while inner.next is not None: if inner.next.val == curr.val: inner.next = inner.next.next else: inner = inner.next curr = curr.next return head

C++

Java

源码分析

删除链表的操作一般判断node.next较为合适，循环时注意inner = inner.next和inner.next = inner.next.next的区别即可。

复杂度分析

两重循环，时间复杂度为 O[12n2]O[\frac{1}{2}n^2]O[​2​​1​​n​2​​], 空间复杂度近似为 O[1]O[1]O[1].

题解2 - 万能的 hashtable

使用辅助空间哈希表，节点值作为键，布尔值作为相应的值（是否为布尔值其实无所谓，关键是键）。

Python

""" Definition of ListNode class ListNode[object]: def __init__[self, val, next=None]: self.val = val self.next = next """ class Solution: """ @param head: A ListNode @return: A ListNode """ def deleteDuplicates[self, head]: if head is None: return None hash = {} hash[head.val] = True curr = head while curr.next is not None: if hash.has_key[curr.next.val]: curr.next = curr.next.next else: hash[curr.next.val] = True curr = curr.next return head

C++

Java

源码分析

删除链表中某个节点的经典模板在while循环中体现。

复杂度分析

遍历一次链表，时间复杂度为 O[n]O[n]O[n], 使用了额外的哈希表，空间复杂度近似为 O[n]O[n]O[n].

Reference