-
Notifications
You must be signed in to change notification settings - Fork 0
/
148.py
51 lines (43 loc) · 1.21 KB
/
148.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
# Sort a linked list in O(n log n) time using constant space complexity.
# Example 1:
# Input: 4->2->1->3
# Output: 1->2->3->4
# Example 2:
# Input: -1->5->3->4->0
# Output: -1->0->3->4->5
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if head == None or head.next == None:
return head
fast = head
slow = head
if fast != None and fast.next != None:
current = slow
fast = fast.next.next
slow = slow.next
current.next = None
return self.merge(self.sortList(slow), self.sortList(head))
def merge(self, a, b) -> ListNode:
"""
merge two sorted linked list
"""
dummy = ListNode()
current = dummy
while a and b:
if a.val >= b.val:
current.next = b
b = b.next
else:
current.next = a
a = a.next
current = current.next
if a:
current.next = a
if b:
current.next = b
return dummy.next