Find duplicates in linked list Python
Ngày đăng:
26/12/2021
Trả lời:
0
Lượt xem:
165
QuestionWrite 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 headC++Java源码分析删除链表的操作一般判断node.next较为合适,循环时注意inner = inner.next和inner.next = inner.next.next的区别即可。 复杂度分析两重循环,时间复杂度为 O(12n2)O(\frac{1}{2}n^2)O(21n2), 空间复杂度近似为 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 headC++Java源码分析删除链表中某个节点的经典模板在while循环中体现。 复杂度分析遍历一次链表,时间复杂度为 O(n)O(n)O(n), 使用了额外的哈希表,空间复杂度近似为 O(n)O(n)O(n). Reference |