Sort a Linked List Using Insertion Sort

Sort a singly linked list using insertion sort, and return the head of the sorted list. Values may repeat.

Example

Text

Input:  8 -> 0 -> 1 -> 3          Output: 0 -> 1 -> 3 -> 8
Input:  -1 -> 7 -> 3 -> 4 -> 2    Output: -1 -> 2 -> 3 -> 4 -> 7

Brute force: insertion sort on the values

Copy the values into an ArrayList, run the textbook insertion sort on it (shift larger values right until the current value fits), and build a new list.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode insertionSortList(ListNode head) {
        List<Integer> values = toList(head);
        for (int i = 1; i < values.size(); i++) {
            int x = values.get(i);
            int j = i;
            while (j > 0 && values.get(j - 1) > x) {
                values.set(j, values.get(j - 1));
                j--;
            }
            values.set(j, x);
        }
        ListNode result = null;
        for (int i = values.size() - 1; i >= 0; i--) {
            result = new ListNode(values.get(i), result);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(toList(insertionSortList(fromArray(8, 0, 1, 3))));
    }
}

Output

[0, 1, 3, 8]

Time: O(n²). Space: O(n) for the copy and the new nodes.

Optimal: move each node into a sorted list

Keep a second list, sorted, which starts empty. Detach nodes from the input one at a time. For each node, walk a prev pointer along sorted (starting at a dummy node before it) past every value <= the node's value, and insert the node after prev. No node is allocated or copied. The nodes use null for "no next node" and have mutable fields, so relinking a node is an assignment.

step	node	sorted after
1	8	8
2	0	0 → 8
3	1	0 → 1 → 8
4	3	0 → 1 → 3 → 8

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static List<Integer> toList(ListNode list) {
        List<Integer> values = new ArrayList<>();
        for (ListNode node = list; node != null; node = node.next) {
            values.add(node.val);
        }
        return values;
    }

    static ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0, null); // the sorted list hangs off dummy.next
        ListNode cur = head;
        while (cur != null) {
            ListNode next = cur.next; // detach cur from the input
            ListNode prev = dummy;
            while (prev.next != null && prev.next.val <= cur.val) {
                prev = prev.next;
            }
            cur.next = prev.next;
            prev.next = cur;
            cur = next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        System.out.println(toList(insertionSortList(fromArray(8, 0, 1, 3))));
        System.out.println(toList(insertionSortList(fromArray(-1, 7, 3, 4, 2))));
        System.out.println(toList(insertionSortList(fromArray(2, 1, 2, 1))));
        System.out.println(toList(insertionSortList(null)));
    }
}

Output

[0, 1, 3, 8]
[-1, 2, 3, 4, 7]
[1, 1, 2, 2]
[]

Time: O(n²) in the worst case, O(n) for input in descending order (each node goes to the front). Space: O(1).

Skipping past equal values (<=) keeps the sort stable. For ascending input, every insertion walks the whole sorted list. Remembering the last inserted node and starting from it when the next value is at least as large fixes that case. For large lists, merge sort gives O(n log n).

Edge cases

Empty list or single node: returned unchanged.
Duplicates: kept in their original relative order.