7.13 Sort List

7.13.1 Problem Metadata

7.13.2 Description

Given the head of a singly linked lc-list, sort the lc-list in ascending order using constant auxiliary space and return the head of the sorted lc-list.

7.13.3 Examples

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

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

7.13.4 Constraints

  • 0 <= n <= 5 * 10^4, where n is the number of nodes
  • -10^5 <= Node.val <= 10^5

7.13.5 Solution - Merge Sort on Linked List

7.13.5.1 Walkthrough

Merge sort divides the linked list at its midpoint, recursively sorts each half, and merges both sorted halves. Use Floyd’s tortoise and hare algorithm with slow/fast pointers to find the middle node. Track midPrev to split the list by setting midPrev.next = null, separating the list into two independent halves. Recursively sort both halves, then merge them using a dummy head approach that compares node values and builds the sorted result.

7.13.5.2 Analysis

  • Time Complexity: O(n log n), merge sort across the lc-list
  • Space Complexity: O(1) auxiliary (recursion stack ignored per problem statement) plus O(log n) call stack

7.13.5.3 Implementation Steps

  1. If the lc-list has zero or one node, return it.
  2. Use slow/fast pointers to find the midpoint; disconnect the first half.
  3. Recursively sort both halves.
  4. Merge the sorted halves with a linear scan and return the merged head.

7.13.5.4 Code - Java

public class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode midPrev = null, slow = head, fast = head;

        while(fast != null && fast.next != null) {
            midPrev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        midPrev.next = null;
        ListNode left = sortList(head);
        ListNode right = sortList(slow);

        return mergeList(left, right);
    }

    private ListNode mergeList(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;

        while(l1 != null && l2 != null) {
            if(l1.val >= l2.val) {
                current.next = l2;
                l2 = l2.next;
            } else {
                current.next = l1;
                l1 = l1.next;
            }

            current = current.next;
        }

        if(l1 != null) {
            current.next = l1;
        } else {
            current.next = l2;
        }

        return dummyHead.next;
    }
}