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
}
​