algorithms_datastructures_python/linked_list_review.py at master · bellaura/algorithms_datastructures_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
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
138
139
140
141
142
143
144
145
146
147
148
class Node:
    def __init__(self, data, next=None):
        self.data = data
        self.next = next

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

    def iterate(self, node=None):
        if node == None:
            node = self.head
        while node:
            print(node.data)
            node = node.next

    def build_from_list(self, items):
        node = None
        for i in range(len(items)-1, -1, -1):
            node = Node(items[i], node)
        self.head = node

    def return_head(self):
        return self.head

def remove_largest(node):
    head = node
    largest_node = node
    before_l = node
    largest = node.data
    if node is None:
        return None
    while node.next:
        if node.next.data > largest:
            largest = node.next.data
            largest_node = node.next
            before_l = node
        node = node.next
    if largest_node == head:
        head = head.next
    else:
        before_l.next = before_l.next.next
    return head

def del_middle_node(node):
    head = node
    f = node
    s = node
    tick = False
    while f.next:
        f = f.next
        if tick:
            b_s = s
            s = s.next
        tick = not tick
    if f == head.next:
        head = head.next
    else:
        b_s.next = b_s.next.next

    return head

f = Node(1)
s = Node(2)
t = Node(3)

f.next = s
s.next = t

ll = Linked_List()
ll.head = f

# ll.iterate()

nums = [9, 7, 5]

ll2 = Linked_List()
ll2.build_from_list(nums)
# ll2.iterate()
# print(ll2.return_head())

ll3 = Linked_List()
largest_removed = remove_largest(ll2.head)
ll3.head = largest_removed

# ll3.iterate()

ll4 = Linked_List()


ll4.head = del_middle_node(ll2.head)
# ll4.iterate()

ll5 = Linked_List()
ll5.build_from_list([9,2,9,3,5,8,5,10,2,1])

def partition(node, val):
    b_n = node
    head = node
    right = False
    while node:
        if node.data < val:
            if node == head:
                node = node.next
            else:
                head = Node(node.data, head)
                b_n.next = node.next
        else:
            right = True
            if right:
                r_e = node
        b_n = node
        node = node.next
    r_e.next = None
    return head

# ll5.iterate()

ll6 = Linked_List()
ll6.head = partition(ll5.head, 5)
# ll6.iterate()


def combine_vals(node):
    total = 0
    mult = 1
    while node:
        val = node.data
        val *= mult
        total += val
        mult *= 10
        node = node.next
    return total


ll7 = Linked_List()
ll7.build_from_list([4, 4, 4])
print(combine_vals(ll7.head))


def add_sums_two_linked(head1, head2):
    total = combine_vals(head1)
    return total + combine_vals(head2)

ll8 = Linked_List()
ll8.build_from_list([4, 4, 4, 4])

print(add_sums_two_linked(ll8.head, ll7.head))