Sort a Linked List

medium linked list merge sort divide and conquer

Problem

Sort a singly-linked list in ascending order using O(n log n) time and constant extra space (apart from recursion stack).

Top-down merge sort: find the midpoint with slow/fast pointers and cut the list in two; recursively sort each half; merge the two sorted halves with a standard two-pointer linked-list merge. Recursion depth is O(log n).

Input4 → 2 → 1 → 3

Output1 → 2 → 3 → 4

Split into [4,2] and [1,3]; sort each into [2,4] and [1,3]; merge to [1,2,3,4].

list (comma-separated)

def sort_list(head):
    if not head or not head.next: return head
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next; fast = fast.next.next
    mid = slow.next; slow.next = None
    L = sort_list(head); R = sort_list(mid)
    dummy = ListNode(); tail = dummy
    while L and R:
        if L.val <= R.val: tail.next = L; L = L.next
        else: tail.next = R; R = R.next
        tail = tail.next
    tail.next = L or R
    return dummy.next

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;
  const L = sortList(head), R = sortList(mid);
  const dummy = { val: 0, next: null }; let tail = dummy;
  let l = L, r = R;
  while (l && r) {
    if (l.val <= r.val) { tail.next = l; l = l.next; }
    else { tail.next = r; r = r.next; }
    tail = tail.next;
  }
  tail.next = l || r;
  return dummy.next;
}

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode mid = slow.next; slow.next = null;
    ListNode L = sortList(head), R = sortList(mid);
    ListNode dummy = new ListNode(), tail = dummy;
    while (L != null && R != null) {
        if (L.val <= R.val) { tail.next = L; L = L.next; }
        else { tail.next = R; R = R.next; }
        tail = tail.next;
    }
    tail.next = (L != null) ? L : R;
    return dummy.next;
}

ListNode* sortList(ListNode* head) {
    if (!head || !head->next) return head;
    ListNode *slow = head, *fast = head->next;
    while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
    ListNode* mid = slow->next; slow->next = nullptr;
    ListNode *L = sortList(head), *R = sortList(mid);
    ListNode dummy(0); ListNode* tail = &dummy;
    while (L && R) {
        if (L->val <= R->val) { tail->next = L; L = L->next; }
        else { tail->next = R; R = R->next; }
        tail = tail->next;
    }
    tail->next = L ? L : R;
    return dummy.next;
}

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