[LeetCode] Challenge log 148

148. Sort List

Merge sort:

  1. if head or head.next is none, return head.
  2. split the list from middle into A and B
  3. recursively merge sort A and B
  4. merge sorted A and sorted B

Complexity:

  • time: Nlog(N)
  • space: recursion call is at most log(N) deep, hence log(N)

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

1
2
Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2
Input: -1->5->3->4->0
Output: -1->0->3->4->5

Soulution:
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
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# split and return two heads
def split(head):
if head is None: return None, None
slow = fast = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
ha = head
hb = slow.next
slow.next = None
return ha, hb

# merge two list
def merge(ha, hb):
if not ha and not hb: return None
head = ListNode(0)
cur = head
while ha and hb:
if ha.val <= hb.val:
cur.next = ha
ha = ha.next
else:
cur.next = hb
hb = hb.next
cur = cur.next
if ha:
cur.next = ha
elif hb:
cur.next = hb
return head.next

# sort
def sort(head):
if head is None or head.next is None:
return head
else:
ha, hb = split(head)
sa = sort(ha)
sb = sort(hb)
return merge(sa,sb)

return sort(head)
0%