-
Notifications
You must be signed in to change notification settings - Fork 4
/
SortList.py
42 lines (34 loc) · 1.13 KB
/
SortList.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
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
def merge_sort(node, length):
if length <= 1:
return node
temp = node
for i in range(0, length // 2 - 1):
temp = temp.next
next_node = temp.next
temp.next = None
left_node = merge_sort(node, length // 2)
right_node = merge_sort(next_node, length - (length // 2))
pre_head = ListNode()
res = pre_head
while left_node and right_node:
if left_node.val <= right_node.val:
pre_head.next = left_node
left_node = left_node.next
else:
pre_head.next = right_node
right_node = right_node.next
pre_head = pre_head.next
pre_head.next = left_node if left_node else right_node
return res.next
list_length = 0
remain = head
while head:
list_length += 1
head = head.next
return merge_sort(remain, list_length)