practice/linked_list.py at master · shoemakerc/practice · GitHub

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
class LinkedList:
    def __init__(self, head=None):
        self.head = head
    def appendToTail(self, data):
        newNode = Node(data)
        if not self.head:
            self.head = newNode
        else:
            n = self.head
            while n.next:
                n = n.next
            n.next = newNode
    def deleteMid(self, badNode):
        newNext = badNode.next
        badNode.data = newNext.data
        badNode.next = badNode.next.next
    def deleteDups(self):
        if not self.head:
            return
        d = {}
        prev = Node()
        n = self.head
        while n:
            if n.data in d:
                prev.next = n.next
            else:
                d[n.data] = 1
                prev = n
            n = n.next
    def printNodes(self):
        if not self.head:
            return
        n = self.head
        while n:
            print(n.getData())
            n = n.next
    def partition(self, n):
        if not self.head or not self.head.next:
            return
        ptr1 = self.head
        ptr2 = self.head.next
        done = False
        while not done:
            while ptr1 and ptr1.data < n:
                ptr1 = ptr1.next
            while ptr2 and ptr2.data >= n:
                ptr2 = ptr2.next
            if not ptr1 or not ptr2:
                done = True
            else:
                ptr1.data, ptr2.data = ptr2.data, ptr1.data
class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None
    def getData(self):
        return self.data
    def getNext(self):
        return self.next
    def setData(self, newData):
        self.data = newData
    def setNext(self, newNext):
        self.next = newNext

def main():
    llist = LinkedList(Node(5))
    llist.appendToTail(4)
    llist.appendToTail(4)
    llist.appendToTail(4)
    llist.appendToTail(1)
    llist.appendToTail(3)
    llist.appendToTail(3)
    llist.appendToTail(4)
    '''
    llist.appendToTail(4)
    llist.appendToTail(4)
    llist.appendToTail(4)
    llist.appendToTail(5)
    '''
    llist.printNodes()
    print("")
    llist.partition(3)
    llist.printNodes()
    print('')
    llist.deleteDups()
    llist.printNodes()
    print('')
    llist2 = LinkedList(Node(2))
    llist2.appendToTail(1)
    llist2.appendToTail(4)
    llist2.appendToTail(4)
    print('')
    llist2.partition(3)
    llist2.printNodes()
main()