noodleProblems/
Sort List
#162

Sort List

AlgorithmmediumLinked ListSortingDivide And ConquerRecursionMerge Sort

Given the head of a singly linked list, sort the list in ascending order and return the head of the sorted list.

Your function receives and returns a ListNode chain; the examples below show each list in array notation for readability — [4, 2, 1, 3] is the chain 4 -> 2 -> 1 -> 3, which sorts to 1 -> 2 -> 3 -> 4. An empty input ([], i.e. head is null) is valid and should return an empty list.

Example cases

  • unsorted
    in head = [4,2,1,3]4213null
    out [1,2,3,4]1234null
  • negatives and duplicates-free mix
    in head = [-1,5,3,4,0]-15340null
    out [-1,0,3,4,5]-10345null
    Negative and non-negative values sort together on one number line.
  • empty list
    in head = []null
    out []null

Constraints

  • The number of nodes in the list is in the range [0, 5 * 10^4].
  • -10^5 <= Node.val <= 10^5
Saved
head =
[4,2,1,3]