Learning-Data-Structures-and-Algorithm-Python/FlattenNestedLinked.py at master · AnushreeBagchi/Learning-Data-Structures-and-Algorithm-Python · 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
96
97
98
99
100
101
102
103
104
105
106
107
class Node:
    def __init__(self,value):
        self.value = value
        self.next = None
    def __repr__(self):
        return str(self.value)

class LinkedList:
    def __init__(self):
        self.head = None
    def createLinkedList(self, inputList):
        self.head = None
        self.tail = None
        for value in inputList:
            if self.head is None:
                self.head = Node(value)
                self.tail = self.head
            else:
                self.tail.next = Node(value)
                self.tail = self.tail.next
    def appendValue(self, value):
        if self.head is None:
            self.head = Node(value)
            return
        node = self.head
        while node.next:
            node = node.next
        node.next = Node(value)
    def appendNode(self, input_node):
        if self.head is None:
            self.head = input_node
            input_node.next = None
            return
        node = self.head
        while node.next:
            node = node.next
        node.next = input_node

    def to_list(self):
        pyList = []
        if self.head :
            node = self.head
            while node:
                pyList.append(node.value)
                node = node.next
        return pyList

# merging sorted linked lists
def merge(llist1, llist2):
    newllist =  LinkedList()
    if llist1 is None:
        return llist2
    elif llist2 is None:
        return llist1
    llist1_node = llist1.head
    llist2_node = llist2.head
    while llist1_node is not None or llist2_node is not None:
        if llist1_node is None:
            newllist.appendNode(llist2_node)
            llist2_node = llist2_node.next
        elif llist2_node is None:
            newllist.appendNode(llist1_node)
            llist1_node = llist1_node.next
        elif llist1_node.value <= llist2_node.value:
            newllist.appendNode(llist1_node)
            llist1_node = llist1_node.next
        else:
            newllist.appendNode(llist2_node)
            llist2_node = llist2_node.next

    return newllist

llistA = LinkedList()
llistA.appendValue(1)
llistA.appendValue(2)
llistA.appendValue(3)
llistA.appendValue(4)
llistA.appendValue(5)


llistB = LinkedList()
llistB.appendValue(21)
llistB.appendValue(31)
llistB.appendValue(41)
llistB.appendValue(51)

llistC = LinkedList()
llistC.appendValue(121)
llistC.appendValue(131)
llistC.appendValue(141)
llistC.appendValue(151)

llistMain = LinkedList()
llistMain.appendValue(llistA)
llistMain.appendValue(llistB)
llistMain.appendValue(llistC)

ll = None
node = llistMain.head
while node.next:
    nextMainNode = node.next
    if ll == None:
        ll = merge(node.value, node.next.value)
    else:
        ll = merge(ll, node.next.value)

    node = nextMainNode