Linked List Comprehensive Problem: Sorting a Linked List - LeetCode by Example

Today’s problem: LeetCode 148 - Sort List (Medium)

Sort a linked list in $O(n \log n)$ time complexity and constant space complexity.

So far in this series, we’ve covered linked list problems in two previous articles: linked list traversal framework in Episode 1 and fast and slow pointers in Episode 5. Linked list problems aren’t that complicated — these two major techniques can already cover most linked list questions.

The linked list sorting problem we’re discussing today is a classic comprehensive linked list problem. In interviews, this question comes up very frequently — it’s even one of a certain Microsoft interviewer’s go-to “three signature questions,” which speaks to how broadly applicable it is. This problem requires various common linked list methods and operations. At the same time, it involves adapting traditional array sorting methods to linked lists, which tests the interviewee’s understanding of sorting algorithms.

Specifically, sorting a linked list tests:

Understanding of linked list properties
Mastery of divide and conquer
Proficiency with linked list operations

Let’s discuss each of these key points one by one.

Sorting Approach

Choosing a Sorting Method

First, we need to understand a fundamental principle of linked list problems: don’t use extra space. Some people find the problem difficult and immediately convert the linked list to an array, then sort the array. This approach is obviously unacceptable. Not using extra space in linked list problems means not creating additional arrays, not creating new linked list nodes — in other words, not using the new keyword.

With this principle in mind, let’s look at the problem. It requires an $O(n \log n)$ sorting algorithm. Looking back at the sorting algorithms we’ve learned, the choice clearly comes down to quicksort, merge sort, or heapsort.

The biggest difference between linked lists and arrays is that linked lists only support sequential access — and even then, only forward sequential access — not random access (access by index). Considering that both quicksort and heapsort involve extensive random access, they must be ruled out. As for the remaining merge sort, upon careful thought, it indeed can work with only sequential access. So we can apply merge sort to linked list sorting.

Adapting Merge Sort to Linked Lists

How do we adapt merge sort to linked lists? We need to review the entire merge sort process. Merge sort is a classic divide-and-conquer algorithm with three steps, like any standard divide-and-conquer approach: divide, conquer, and combine.

Divide: Split the array in half — $O(1)$ time;
Conquer: Recursively sort each half — each half is a subproblem of size $n/2$ ;
Combine: Merge the two sorted halves into one — $O(n)$ time.

According to the master theorem, the time complexity of this divide-and-conquer algorithm is $O(n \log n)$ .

So what does this algorithm look like when applied to linked lists?

Divide: Since we can’t randomly access the midpoint of the list, we need a sequential traversal — $O(n)$ time;
Conquer: Same as array sorting;
Combine: Can be done with sequential traversal alone, same as array sorting — $O(n)$ time.

As you can see, although the divide step went from $O(1)$ to $O(n)$ , this doesn’t exceed the time of the combine step. Since the master theorem considers the total time of the divide and combine steps, the time complexity for linked list sorting is the same as array sorting: $O(n \log n)$ . We’ve met the time complexity requirement — now let’s see how each step works in practice.

Splitting the Linked List

Splitting the linked list requires dividing it into two halves. This operation can actually be broken down into two basic operations:

Finding the midpoint of the linked list
Removing the pointer to the left of the midpoint to break the list apart

Finding the midpoint of a linked list was covered in the fast and slow pointers article — just use two pointers, one fast and one slow, to traverse the list.

Removing a linked list pointer is similar to deleting a linked list node. As we discussed in the linked list traversal framework article, you use two adjacent pointers traversing the list together.

How do we combine these two techniques? We use three pointers: a fast pointer, a slow pointer, and a pointer to the node before the slow pointer. When the fast pointer reaches the end of the list, the node before the slow pointer is exactly where we need to cut.

ListNode split(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    ListNode prev = null;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        prev = slow;
        slow = slow.next;
    }
    prev.next = null; // Break the linked list apart
    return slow;
}

Although the pointer operations in the code look complex, as long as you understand the two basic dual-pointer operations for linked lists, writing this is quite manageable.

Merging Linked Lists

How do we merge two sorted linked lists into one sorted linked list? Linked list merging is actually a fundamental operation — for example, this problem tests exactly that:

LeetCode 21 - Merge Two Sorted Lists (Easy)

If you haven’t done this problem before, no worries — let’s look at how the merge code works in array-based merge sort. The following code is from Sedgewick’s Algorithms, 4th Edition:

void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
    // copy to aux[]
    for (int k = lo; k <= hi; k++) {
        aux[k] = a[k]; 
    }

    // merge back to a[]
    int i = lo, j = mid+1;
    for (int k = lo; k <= hi; k++) {
        if      (i > mid)              a[k] = aux[j++];
        else if (j > hi)               a[k] = aux[i++];
        else if (less(aux[j], aux[i])) a[k] = aux[j++];
        else                           a[k] = aux[i++];
    }
}

The idea behind array merging is straightforward. Two pointers i and j point to the next element to be merged from each array, and each time we pick the smaller element and append it to the new array. The four conditional branches handle:

The case where one of the arrays has been exhausted (two branches)
If both arrays still have elements, compare their values (two branches)

If we replace every mention of “array” in the above approach with “linked list,” we essentially get the linked list merge method. However, since we constantly need to insert nodes at the tail of the linked list, the code is a bit more verbose.

// Global variables for inserting nodes at the list tail
ListNode head;
ListNode tail;

ListNode merge(ListNode left, ListNode right) {
    head = null;
    tail = null;
    ListNode q1 = left;
    ListNode q2 = right;
    while (q1 != null || q2 != null) {
        if (q1 == null) {
            append(q2);
            q2 = q2.next;
        } else if (q2 == null) {
            append(q1);
            q1 = q1.next;
        } else if (q1.val < q2.val) {
            append(q1);
            q1 = q1.next;
        } else {
            append(q2);
            q2 = q2.next;
        }
    }
    return head;
}

void append(ListNode node) {
    if (head == null) {
        head = node;
        tail = node;
    } else {
        tail.next = node;
        tail = node;
    }
}

Complete Code

At this point, all the code for linked list sorting is complete. Here is the full solution:

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode mid = split(head);
    ListNode left = sortList(head);
    ListNode right = sortList(mid);
    return merge(left, right);
}

ListNode split(ListNode head) {
    ListNode fast = head;
    ListNode slow = head;
    ListNode prev = null;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        prev = slow;
        slow = slow.next;
    }
    prev.next = null;
    return slow;
}

ListNode head;
ListNode tail;

ListNode merge(ListNode left, ListNode right) {
    head = null;
    tail = null;
    ListNode q1 = left;
    ListNode q2 = right;
    while (q1 != null || q2 != null) {
        if (q1 == null) {
            append(q2);
            q2 = q2.next;
        } else if (q2 == null) {
            append(q1);
            q1 = q1.next;
        } else if (q1.val < q2.val) {
            append(q1);
            q1 = q1.next;
        } else {
            append(q2);
            q2 = q2.next;
        }
    }
    return head;
}

void append(ListNode node) {
    if (head == null) {
        head = node;
        tail = node;
    } else {
        tail.next = node;
        tail = node;
    }
}

Summary

The linked list sorting problem isn’t hard on its own, but as a comprehensive problem, it tests knowledge across many areas. We need to understand basic operations like the linked list traversal framework and fast/slow pointers, know the properties of linked lists well enough to choose an appropriate sorting algorithm, and transfer knowledge from existing array sorting methods. If you’re preparing for interviews, it’s worth practicing this problem until you’re comfortable with it — it serves as an excellent summary of linked list problems.