LeetCode-in-All
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
import "slices"
type ListNode struct {
Val int
Next *ListNode
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func sortList(head *ListNode) *ListNode {
curr := head
a := []*ListNode{}
for curr != nil {
a = append(a, curr)
curr = curr.Next
}
slices.SortFunc(a, func(l1, l2 *ListNode) int {
return l1.Val - l2.Val
})
newNode := &ListNode{}
curr = newNode
for _, node := range a {
curr.Next = node
curr = node
}
curr.Next = nil
return newNode.Next
}