Delete duplicates from a singly linked list

25.03.2015

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
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()       
|