PythonPrep/ll.py at main · rrahul-1/PythonPrep · 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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
from collections import deque
class Node:
    def __init__(self,val = None,next = None):
        self.val = val
        self.next = next

class ll:
    def __init__(self):
        self.head = None

    def add_last(self, val):
        if not self.head:
            self.head = Node(val)
        else:
            head = self.head
            t = Node(val)
            while head.next:
                head = head.next
            head.next = t
    def display(self):
        head = self.head
        while head:
            print(head.val, ' --> ', end='')
            head = head.next
        print()

    def add_rec(self,val,pos,head,prev=None):
        if pos == 0:
            t = Node(val,head)
            if prev:
                prev.next = t
            else:
                self.head = t
            return
        self.add_rec(val,pos-1,head.next,head)

    def mid(self, head):
        fp = sp = prev = head
        while fp and fp.next:
            prev = sp
            sp = sp.next
            fp = fp.next.next
        prev.next = None
        return sp

    def merge(self, f, s):
        res = Node()
        ans = res
        while f and s:
            if f.val < s.val:
                ans.next = f
                f = f.next
                ans = ans.next
            else:
                ans.next = s
                s = s.next
                ans = ans.next
        if f:
            ans.next = f
        if s:
            ans.next = s
        return res.next

    def mergesort(self, head):
        if not head or not head.next:
            return head

        mid = self.mid(head)
        left = self.mergesort(head)
        right = self.mergesort(mid)

        return self.merge(left, right)

    def reverse(self):
        head = self.head
        prev = None
        while head:
            t = head.next
            head.next = prev
            prev = head
            head = t
        self.head = prev

    def reverse_rec(self,head):
        if not head.next:
            self.head = head
            return head

        node = self.reverse_rec(head.next)

        node.next = head
        head.next = None
        return head


    res = deque()
    max = 0
    def rec(self, head):
        if not head.next:
            self.res.appendleft(0)
            self.max = head.val
            return

        self.rec(head.next)
        if self.max < head.val:
            self.res.appendleft(0)
            self.max = head.val
        else:
            self.res.appendleft(self.max)

    def nextLargerNodes(self, head):
        self.rec(head)
        return self.res

if __name__ == '__main__':
    list = ll()
    arr = [2,7,4,3,5]
    arr= [2,1,5]
    for i in arr:
        list.add_last(i)
    list.display()
    '''
    list.add_rec(4,3,list.head)
    list.add_last(0)
    list.add_last(5  )
    list.display()
    list.head = list.mergesort(list.head)
    list.display()
    list.reverse()
    list.display()
    list.reverse_rec(list.head)
    list.display()
    '''
    arr = list.nextLargerNodes(list.head)
    print(list(arr))