148. Sort List

Medium

Given the head of a linked list, return the list after sorting it in ascending order.

Example 1:

Input: head = [4,2,1,3]
Output:
 [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output:
 [-1,0,3,4,5]

Example 3:

Input: head = []
Output:
 []

Constraints:

• The number of nodes in the list is in the range [0, 5 * 104].

• -105 <= Node.val <= 105

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

解題

Divide and Conquer.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil { //在只有一個元素以前，會不斷切割
        return head
    }

    fast, slow, preSlow := head, head, head

    for fast != nil && fast.Next != nil {
        preSlow = slow
        slow = slow.Next
        fast = fast.Next.Next
    }

    preSlow.Next = nil // 將 linked list 斷為兩半
    
    l1 := sortList(head)
    l2 := sortList(slow)

    return merge(l1, l2) 
}

func merge(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil { return l2 }
    if l2 == nil { return l1 }

    res := &ListNode{} 
    cur := res
    
    for l1 != nil && l2 != nil {

        if l1.Val < l2.Val {
            cur.Next = l1 // 把比較小的接到要回傳之 linked list 尾端
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }

        cur = cur.Next
    }
    
    // 處理兩陣列長度不一之情況
    for l1 != nil { 
        cur.Next = l1
        l1 = l1.Next
        cur = cur.Next
    }
    
    for l2 != nil {
        cur.Next = l2
        l2 = l2.Next
        cur = cur.Next
    }

    return res.Next
}