leetcode148

Posted on | In

148. Sort List

Description

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

Idea

merge sort, divide and conquer

Code

body

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def sortList(self, head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    # base case:
    if head is None or head.next is None:
        return head
    
    # divide
    mid = self.findMid(head)
    next_head = mid.next
    mid.next = None
    sorted_left = self.sortList(head)
    sorted_right = self.sortList(next_head)

    # conquer
    res = self.merge(sorted_left, sorted_right)
    return res

find middle: fast and slow pointer

1
2
3
4
5
6
7
8
9
10
def findMid(self, head):
    if head is None:
        return None
    runner = head
    walker = head
    while runner.next and runner.next.next:
    # error while walker.next and runner.next.next:
        walker = walker.next
        runner = runner.next.next
    return walker

merge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def merge(self, head1, head2):
    dummy = ListNode(0)
    cur = dummy
    p1 = head1
    p2 = head2

    # perform the normal case
    while p1 and p2:
        if p1.val < p2.val:
            cur.next = ListNode(p1.val)
            p1 = p1.next
        else:
            cur.next = ListNode(p2.val)
            p2 = p2.next
        cur = cur.next

    # handle the rest list
    if p1:
        cur.next = p1
    if p2:
        cur.next = p2
    return dummy.next