Sort List Medium 0 attempts
LeetCode ↗

Sort List

Medium Linked List LeetCode

Given the head of a singly linked list, rearrange its nodes into ascending order and return the new head. Aim for O(n log n) time complexity, ideally using only constant (O(1)) extra space.

Input Format
Implement sortList(head). Inputs below show JavaScript function arguments; there is no stdin parsing. Linked lists use value arrays. The editor passes nodes with val and next properties; [] becomes null.
Output Format
Return the result described in the statement. Returned list heads are displayed as value arrays; a null head is [].

Sample Input and Output

Example 1 ยท Run Sample

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

Example 2

Input
head = []
Output
[]
Constraints
  • 0 to 5 * 10^4 nodes
  • -10^5 <= Node.val <= 10^5
Test Cases (2)
Case 1
Args: [[4,2,1,3]] Expected: [1,2,3,4]
Case 2
Args: [[]] Expected: []
Topics
Linked List

Merge Sort

javascript
function sortList(head) {
  if (!head || !head.next) return head;
  let slow = head, fast = head.next;
  while (fast && fast.next) { slow = slow.next; fast = fast.next.next; }
  const mid = slow.next; slow.next = null;
  return merge(sortList(head), sortList(mid));
}
function merge(a, b) {
  const d = {next:null}; let t = d;
  while (a&&b) { if (a.val<=b.val) { t.next=a; a=a.next; } else { t.next=b; b=b.next; } t=t.next; }
  t.next = a||b; return d.next;
}

Time: O(n log n) | Space: O(log n)

Saved in this browser only. Private to you.

JavaScript