---

1. Problem Summary

You are given the head of a singly linked list.
Your task is to sort the linked list in ascending order using the logic of insertion sort, and return the new head.

Important characteristics:

• Sorting must simulate insertion sort behavior
• You cannot index nodes directly (linked list limitation)
• You must adjust node pointers rather than swap values (best practice)
• The list may contain duplicates, negative values, or already sorted segments

Example interpretation:
For input:

4 → 2 → 1 → 3

Sorted output:

1 → 2 → 3 → 4

---

2. Key Insights

Why standard insertion sort fits linked lists

Insertion sort inserts elements into their correct place in a growing sorted region.
Linked lists allow efficient insertion when the insertion point is known.

Main strategy

Maintain two conceptual regions:

1. A sorted portion at the beginning
2. The remaining unsorted nodes

Each iteration extracts the next unsorted node and inserts it into the correct position in the sorted region.

Dummy head simplifies insertion logic

Using a dummy node avoids edge-case handling when inserting at the head.

Traversal rule for insertion position

For each node being inserted:

find first node in sorted region whose value > current.val
insert before it

---

3. Approach

Linked list insertion sort with dummy head

Steps:

1. Create a dummy head (dummy) whose next points to null
2. Traverse the original list with pointer current
3. For each node:
   • Store nextNode = current.next
   • Find insertion point starting from dummy
   • Insert the node into sorted position
   • Move current = nextNode
4. Continue until entire list is processed
5. Return dummy.next as sorted head

This guarantees correctness and handles insert-at-head cleanly.

---

4. Time and Space Complexity

Time Complexity: O(N²)

Worst case: descending list causes full scans for each insertion.

Space Complexity: O(1)

Sorting done in-place, no extra list storage used.

---

5. Java Solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode current = head;

        while (current != null) {
            ListNode nextNode = current.next;

            // Find insertion position
            ListNode prev = dummy;
            while (prev.next != null && prev.next.val < current.val) {
                prev = prev.next;
            }

            // Insert current node
            current.next = prev.next;
            prev.next = current;

            // Move to next original node
            current = nextNode;
        }

        return dummy.next;
    }
}

---

6. Dry Run Examples

Example 1

Input:

4 → 2 → 1 → 3

Processing:

Start with dummy → []

Insert 4:

dummy → 4

Insert 2:
find position before 4

dummy → 2 → 4

Insert 1:
find position before 2

dummy → 1 → 2 → 4

Insert 3:
find position between 2 and 4

dummy → 1 → 2 → 3 → 4

Output:

1 → 2 → 3 → 4

---

Example 2

Input:

-1 → 5 → 3 → 4 → 0

Sorted result:

-1 → 0 → 3 → 4 → 5

---

Example 3 (already sorted)

Input:

1 → 2 → 3

Insertion positions always at end
Output same list

---

Example 4 (reverse sorted)

Input:

5 → 4 → 3 → 2 → 1

Worst-case behavior
Output:

1 → 2 → 3 → 4 → 5

---

7. Why This Solution Works

• Simulates insertion sort exactly
• Uses dummy head to simplify edge insertion
• Avoids value swapping (pointer manipulation preferred)
• Handles duplicates without special cases
• Works for all list lengths including size 0 or 1

---

8. Common Mistakes

1. Forgetting to store nextNode before insertion (loses remainder of list)
2. Trying to swap node values instead of inserting nodes
3. Incorrectly resetting search pointer (must restart from dummy each time)
4. Breaking sorted chain due to pointer misassignment
5. Assuming array-style indexing works