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()