LeetCode-in-Go
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)?
Solution
type ListNode struct {
Val int
Next *ListNode
}
/**
* 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
}
mid := findMid(head)
left := sortList(head)
right := sortList(mid)
return merge(left, right)
}
func findMid(head *ListNode) *ListNode {
var prev *ListNode
slow, fast := head, head
for fast != nil && fast.Next != nil {
prev = slow
slow = slow.Next
fast = fast.Next.Next
}
prev.Next = nil
return slow
}
func merge(left, right *ListNode) *ListNode {
pointer := new(ListNode)
res := pointer
for left != nil && right != nil {
if left.Val < right.Val {
pointer.Next = left
left = left.Next
} else {
pointer.Next = right
right = right.Next
}
pointer = pointer.Next
}
if left != nil {
pointer.Next = left
}
if right != nil {
pointer.Next = right
}
return res.Next
}