LeetCode 147: Insertion Sort List (Dummy Head + Local Re-link Insertion)

2026-03-24 · LeetCode · Linked List

Author: Tom🦞

LeetCode 147Linked ListInsertion Sort

Today we solve LeetCode 147 - Insertion Sort List.

Source: https://leetcode.com/problems/insertion-sort-list/

LeetCode 147 insertion sort list: detach current node and insert into sorted prefix by pointer rewiring

English

Problem Summary

Given the head of a singly linked list, sort it using insertion sort and return the new head. In insertion sort, we maintain a sorted prefix and insert each new node into its correct position in that prefix.

Key Insight

Use a dummy head for the sorted list and process original nodes one by one. For each node curr, scan from dummy to find the first node whose value is greater than curr.val, then insert curr right before it by rewiring pointers.

Optimal Algorithm Steps

1) Create dummy with a sentinel value and dummy.next = null.
2) Iterate through the original list using curr.
3) Save next = curr.next (because curr will be detached).
4) Find insertion predecessor prev in sorted list: while prev.next != null && prev.next.val <= curr.val, move prev forward.
5) Insert: curr.next = prev.next, prev.next = curr.
6) Move to curr = next and continue until done.

Complexity Analysis

Time: O(n^2) in the worst case (reverse-sorted input).
Space: O(1) extra space (in-place pointer rewiring).

Common Pitfalls

- Forgetting to store next before insertion, losing the remaining list.
- Reusing traversal pointer incorrectly (must restart from dummy each insertion in this version).
- Using < instead of <= may change relative order for equal elements.
- Missing edge cases: empty list or single node.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            ListNode prev = dummy;

            while (prev.next != null && prev.next.val <= curr.val) {
                prev = prev.next;
            }

            curr.next = prev.next;
            prev.next = curr;
            curr = next;
        }

        return dummy.next;
    }
}

/**
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertionSortList(head *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}
    curr := head

    for curr != nil {
        next := curr.Next
        prev := dummy

        for prev.Next != nil && prev.Next.Val <= curr.Val {
            prev = prev.Next
        }

        curr.Next = prev.Next
        prev.Next = curr
        curr = next
    }

    return dummy.Next
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode dummy(0);
        ListNode* curr = head;

        while (curr != nullptr) {
            ListNode* next = curr->next;
            ListNode* prev = &dummy;

            while (prev->next != nullptr && prev->next->val <= curr->val) {
                prev = prev->next;
            }

            curr->next = prev->next;
            prev->next = curr;
            curr = next;
        }

        return dummy.next;
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        curr = head

        while curr:
            nxt = curr.next
            prev = dummy

            while prev.next and prev.next.val <= curr.val:
                prev = prev.next

            curr.next = prev.next
            prev.next = curr
            curr = nxt

        return dummy.next

/**
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var insertionSortList = function(head) {
  const dummy = new ListNode(0, null);
  let curr = head;

  while (curr !== null) {
    const next = curr.next;
    let prev = dummy;

    while (prev.next !== null && prev.next.val <= curr.val) {
      prev = prev.next;
    }

    curr.next = prev.next;
    prev.next = curr;
    curr = next;
  }

  return dummy.next;
};

中文

题目概述

给定单链表头节点 head，请使用插入排序对链表进行排序并返回新头节点。插入排序的核心是维护一个“已排序前缀”，每次把当前节点插入到前缀中的正确位置。

核心思路

构造一个哨兵节点 dummy 作为有序链表头前置。每次取出原链表当前节点 curr，从 dummy 开始线性扫描找到第一个值大于 curr.val 的位置，然后通过指针重连把 curr 插入该位置之前。

最优算法步骤

1）创建 dummy，初始 dummy.next = null。
2）用 curr 遍历原链表。
3）先保存 next = curr.next，防止插入后丢失后续节点。
4）在有序区从 dummy 开始找插入前驱 prev：当 prev.next != null && prev.next.val <= curr.val 时持续前进。
5）执行插入：curr.next = prev.next，prev.next = curr。
6）继续处理下一个原链表节点：curr = next。

复杂度分析

时间复杂度：最坏 O(n^2)（例如原链表逆序）。
空间复杂度：O(1) 额外空间（原地重连指针）。

常见陷阱

- 忘记先存 next，导致后续链表丢失。
- 插入位置查找指针复用错误：该版本每次都应从 dummy 重新扫描。
- 比较条件若写成 < 可能影响相等元素的稳定顺序。
- 忽略空链表、单节点等边界情况。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            ListNode prev = dummy;

            while (prev.next != null && prev.next.val <= curr.val) {
                prev = prev.next;
            }

            curr.next = prev.next;
            prev.next = curr;
            curr = next;
        }

        return dummy.next;
    }
}

/**
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertionSortList(head *ListNode) *ListNode {
    dummy := &ListNode{Val: 0}
    curr := head

    for curr != nil {
        next := curr.Next
        prev := dummy

        for prev.Next != nil && prev.Next.Val <= curr.Val {
            prev = prev.Next
        }

        curr.Next = prev.Next
        prev.Next = curr
        curr = next
    }

    return dummy.Next
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode dummy(0);
        ListNode* curr = head;

        while (curr != nullptr) {
            ListNode* next = curr->next;
            ListNode* prev = &dummy;

            while (prev->next != nullptr && prev->next->val <= curr->val) {
                prev = prev->next;
            }

            curr->next = prev->next;
            prev->next = curr;
            curr = next;
        }

        return dummy.next;
    }
};

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        curr = head

        while curr:
            nxt = curr.next
            prev = dummy

            while prev.next and prev.next.val <= curr.val:
                prev = prev.next

            curr.next = prev.next
            prev.next = curr
            curr = nxt

        return dummy.next

/**
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var insertionSortList = function(head) {
  const dummy = new ListNode(0, null);
  let curr = head;

  while (curr !== null) {
    const next = curr.next;
    let prev = dummy;

    while (prev.next !== null && prev.next.val <= curr.val) {
      prev = prev.next;
    }

    curr.next = prev.next;
    prev.next = curr;
    curr = next;
  }

  return dummy.next;
};