LeetCode 147: Insertion Sort List Solution in Python Explained

Problem Statement

In LeetCode 147, you’re given the head of a singly linked list. Your task is to sort it in ascending order using insertion sort and return the head of the sorted list. Insertion sort builds a sorted portion by inserting each unsorted node into its correct position. This differs from cache management like LeetCode 146: LRU Cache, focusing on list sorting rather than data structure operations.

Constraints

• Number of nodes: 1 <= n <= 10^4
• Node values: -5000 <= Node.val <= 5000

Example

Let’s see some cases:

Copy codeInput: head = [4,2,1,3]
Output: [1,2,3,4]
Explanation: 
<ul>
<li>Original: 4->2->1->3</li>
<li>Sorted: 1->2->3->4</li>
</ul>

Copy codeInput: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]
Explanation: 
<ul>
<li>Original: -1->5->3->4->0</li>
<li>Sorted: -1->0->3->4->5</li>
</ul>

Copy codeInput: head = [1]
Output: [1]
Explanation: Single node, already sorted.

These examples show we’re sorting the list using insertion sort.

Understanding the Problem

How do you solve LeetCode 147: Insertion Sort List in Python? Take head = [4,2,1,3]. We need to sort it to 1->2->3->4 using insertion sort—start with 4, insert 2 before 4, insert 1 before 2, insert 3 between 2 and 4. For [-1,5,3,4,0], it becomes -1->0->3->4->5. This isn’t a tree traversal like LeetCode 145: Binary Tree Postorder Traversal; it’s about linked list sorting. We’ll use: 1. Insertion Sort with Dummy Node: O(n²) time, O(1) space—our best solution. 2. Array Conversion with Sorting: O(n log n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Insertion Sort with Dummy Node Approach

Explanation

Insertion Sort with Dummy Node uses a dummy node to simplify insertion at the start, maintaining a sorted portion of the list. For each unsorted node, traverse the sorted portion to find its insertion point, adjusting pointers in-place. This is the best solution due to its O(n²) time complexity (standard for insertion sort), O(1) space usage (no extra structures beyond pointers), and adherence to the problem’s linked list focus, making it efficient and true to the algorithm’s intent.

For [4,2,1,3]:

• Sorted: 4.
• Insert 2: 2->4.
• Insert 1: 1->2->4.
• Insert 3: 1->2->3->4.

Step-by-Step Example

Assume a ListNode class: class ListNode: def __init__(self, val=0, next=None): self.val = val; self.next = next.

Example 1: head = [4,2,1,3]

Goal: Return [1,2,3,4].

• Start: dummy = Node(0), dummy.next = 4->2->1->3, curr = 4.
• Step 1: curr = 4, sorted = 4, curr = 2.
• Step 2: curr = 2, insert 2 before 4:
• prev = dummy, prev.next = 4, 2 < 4, insert after dummy.
• Sorted: 2->4, curr = 1.
• Step 3: curr = 1, insert 1 before 2:
• prev = dummy, prev.next = 2, 1 < 2, insert after dummy.
• Sorted: 1->2->4, curr = 3.
• Step 4: curr = 3, insert 3 between 2 and 4:
• prev = 2, prev.next = 4, 3 < 4, insert after 2.
• Sorted: 1->2->3->4, curr = null.
• Finish: Return dummy.next = 1.

Example 2: head = [-1,5,3,4,0]

Goal: Return [-1,0,3,4,5].

• Start: dummy.next = -1->5->3->4->0, curr = -1.
• Step 1: curr = -1, sorted = -1, curr = 5.
• Step 2: curr = 5, -1 < 5, sorted = -1->5, curr = 3.
• Step 3: curr = 3, insert 3 between -1 and 5, sorted = -1->3->5, curr = 4.
• Step 4: curr = 4, insert 4 between 3 and 5, sorted = -1->3->4->5, curr = 0.
• Step 5: curr = 0, insert 0 between -1 and 3, sorted = -1->0->3->4->5`.
• Finish: Return -1.

Example 3: head = [1]

Goal: Return [1].

• Start: dummy.next = 1, curr = 1.
• Step 1: curr = 1, sorted = 1, curr = null.
• Finish: Return 1.

How the Code Works (Insertion Sort with Dummy Node) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

Copy codeclass ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def insertionSortList(head: ListNode) -> ListNode:
    # Line 1: Handle null or single node cases
    if not head or not head.next:
        # If head is None or single (e.g., [1]), already sorted
        return head

    # Line 2: Initialize dummy node and current pointer
    dummy = ListNode(0)
    # Dummy head for sorted list (e.g., 0)
    dummy.next = head
    # Link to original list (e.g., 0->4->2->...)
    curr = head.next
    # Start at second node (e.g., 2)
    head.next = None
    # First node becomes sorted portion (e.g., 4)

    # Line 3: Iterate over unsorted nodes
    while curr:
        # curr = node to insert (e.g., 2, then 1)

        # Line 4: Find insertion point in sorted list
        prev = dummy
        # Start at dummy (e.g., 0)
        while prev.next and prev.next.val < curr.val:
            # Move until correct spot (e.g., 4 < 2 false)
            prev = prev.next
            # e.g., stays at 0 for 2

        # Line 5: Insert current node
        temp = curr.next
        # Save next unsorted node (e.g., 1)
        curr.next = prev.next
        # Link to sorted next (e.g., 2->4)
        prev.next = curr
        # Link prev to curr (e.g., 0->2)
        curr = temp
        # Move to next unsorted (e.g., 1)
        # e.g., after 2: 0->2->4, curr=1

    # Line 6: Return sorted list head
    return dummy.next
    # Final sorted list (e.g., 1->2->3->4)

This detailed breakdown clarifies how insertion sort with a dummy node efficiently sorts the list.

Alternative: Array Conversion with Sorting Approach

Explanation

Array Conversion with Sorting converts the linked list to an array, sorts it using Python’s O(n log n) sort, and rebuilds the list. It’s a practical alternative, simpler with O(n log n) time, but uses O(n) space and doesn’t strictly follow insertion sort, making it less aligned with the problem’s intent.

For [4,2,1,3]:

• Array: [4,2,1,3] → [1,2,3,4].
• Rebuild: 1->2->3->4.

Step-by-Step Example (Alternative)

For [4,2,1,3]:

• Step 1: arr = [4,2,1,3].
• Step 2: Sort arr = [1,2,3,4].
• Step 3: Rebuild 1->2->3->4.
• Finish: Return 1.

How the Code Works (Array Conversion)

Copy codedef insertionSortListArray(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    arr = []
    curr = head
    while curr:
        arr.append(curr.val)
        curr = curr.next
    arr.sort()
    new_head = ListNode(arr[0])
    curr = new_head
    for val in arr[1:]:
        curr.next = ListNode(val)
        curr = curr.next
    return new_head

Complexity

• Insertion Sort with Dummy Node:
• Time: O(n²) – insertion sort comparisons.
• Space: O(1) – constant space.
• Array Conversion with Sorting:
• Time: O(n log n) – array sort.
• Space: O(n) – array storage.

Efficiency Notes

Insertion Sort with Dummy Node is the best solution with O(n²) time and O(1) space, adhering to the problem’s insertion sort requirement—Array Conversion with Sorting is faster at O(n log n) but uses O(n) space and deviates from insertion sort, making it a practical but less faithful alternative.

Key Insights

• Insertion Sort: Builds sorted portion.
• Dummy Node: Simplifies insertion.
• Array: Faster but space-heavy.

Additional Example

For head = [3,1,4]:

• Goal: [1,3,4].
• Insertion: 3, insert 1->3, insert 1->3->4.

Edge Cases

• Single Node: [1] → [1].
• Two Nodes: [2,1] → [1,2].
• Duplicates: [1,1] → [1,1].

Both solutions handle these well.

Final Thoughts

LeetCode 147: Insertion Sort List in Python is a classic sorting challenge. The Insertion Sort with Dummy Node solution excels with its space efficiency and fidelity, while Array Conversion with Sorting offers a faster alternative. Want more? Try LeetCode 148: Sort List for merge sort or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 147 on LeetCode with [4,2,1,3], aiming for [1,2,3,4]—test your skills now!