forked from haoel/leetcode
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathsortList.py
More file actions
37 lines (33 loc) · 882 Bytes
/
sortList.py
File metadata and controls
37 lines (33 loc) · 882 Bytes
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
# merge sort:
def sortList(self, head):
if not head or not head.next: return head
leftHalf, rightHalf = self.split(head)
left = self.sortList(leftHalf)
right = self.sortList(rightHalf)
return self.mergeSorted(left, right)
def mergeSorted(self, a, b):
res = dummy = ListNode(0)
while a and b:
if a.val < b.val:
dummy.next = a
dummy = a
a = a.next
else:
dummy.next = b
dummy = b
b = b.next
if not a: dummy.next = b
else: dummy.next = a
return res.next
def split(self, node):
if not node or not node.next:
return node, None
slow, fast = node, node
prev = None
while fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
if not fast: break
prev.next = None
return node, slow