-
Notifications
You must be signed in to change notification settings - Fork 891
/
problem_169.py
94 lines (70 loc) · 1.79 KB
/
problem_169.py
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
import sys
class Node:
def __init__(self, x):
self.val = x
self.next = None
def __str__(self):
string = "["
node = self
while node:
string += "{} ->".format(node.val)
node = node.next
string += "None]"
return string
def get_nodes(values):
next_node = None
for value in values[::-1]:
node = Node(value)
node.next = next_node
next_node = node
return next_node
def get_list(head):
node = head
nodes = list()
while node:
nodes.append(node.val)
node = node.next
return nodes
def merge_sorted_lists(list_a, list_b):
head = Node(-sys.maxsize)
node = head
node_a = list_a
node_b = list_b
while node_a and node_b:
if node_a.val < node_b.val:
tmp = node_a
node_a = node_a.next
else:
tmp = node_b
node_b = node_b.next
tmp.next = None
node.next = tmp
node = node.next
if node_a:
node.next = node_a
if node_b:
node.next = node_b
return head.next
def sort_ll_helper(llist, node_count):
if node_count == 1:
return llist
mid = node_count // 2
right_head = llist
left_tail = None
for _ in range(mid):
left_tail = right_head
right_head = right_head.next
left_tail.next = None
sorted_left = sort_ll_helper(llist, mid)
sorted_right = sort_ll_helper(right_head, node_count - mid)
return merge_sorted_lists(sorted_left, sorted_right)
def sort_ll(llist):
count = 0
node = llist
while node:
count += 1
node = node.next
return sort_ll_helper(llist, count)
# Tests
llist = get_nodes([4, 1, -3, 99])
assert get_list(sort_ll(llist)) == [-3, 1, 4, 99]