Delete duplicates from a singly linked list
I can use a buffer, and that runs in O(N)
, or I can use no buffer and runner pointers and that runs in O(N^2)
.
class Node(object): def __init__(self, value): self.value = value self.next = None class LinkedList(object): head = None def append(self, value): new_node = Node(value) if self.head is None: self.head = new_node return n = self.head while n.next is not None: n = n.next n.next = new_node def show(self): n = self.head while n is not None: print n.value, n = n.next print def delDup(self): l = [] n = self.head l.append(n.value) while n.next is not None: if n.next.value in l: n.next = n.next.next else: l.append(n.next.value) n = n.next def delDupNoBuf(self): current = self.head while current is not None: runner = current while runner.next is not None: if runner.next.value == current.value: runner.next = runner.next.next else: runner = runner.next current = current.next l = LinkedList() l.append(10) l.append(10) l.append(20) l.append(10) l.delDup() l.append(20) l.delDupNoBuf() l.show()