LeetCode 147 对链表进行插入排序：O(1)空间实现排序

题目描述

给定单个链表的头节点 head ，使用 插入排序 对链表进行排序，并返回排序后链表的头节点。

插入排序 算法的步骤:

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入: head = [4,2,1,3]
输出: [1,2,3,4]

示例 2：

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

提示

• 链表中节点的数目在范围 [1, 5000] 内
• -5000 <= Node.val <= 5000

---

解题思路

链表插入排序

插入排序的基本思想是构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到合适位置插入。

关键点：

1. 维护已排序部分和未排序部分
2. 用哑节点（dummy node）简化插入操作
3. 优化：如果当前节点值 >= 已排序部分的最后一个节点，就不用插入了

具体步骤：

1. 创建哑节点，next指向head
2. lastSorted指向已排序部分的最后一个节点，初始为head
3. curr指向待插入节点，初始为head.next
4. 对于每个待插入节点：
   • 值 >= lastSorted，无需插入
   • 否则，从头遍历找插入位置
   • 执行插入操作
5. 重复直到处理完所有节点

时间复杂度：O(n²)，n 是链表长度 空间复杂度：O(1)，只用常数额外空间

图解思路

以示例1为例，演示排序过程：

1. 初始状态：

dummy -> 4 -> 2 -> 1 -> 3
lastSorted = 4
curr = 2

2. 处理节点2：

dummy -> 2 -> 4 -> 1 -> 3
lastSorted = 4
curr = 1

3. 处理节点1：

dummy -> 1 -> 2 -> 4 -> 3
lastSorted = 4
curr = 3

4. 处理节点3：

dummy -> 1 -> 2 -> 3 -> 4
lastSorted = 4
curr = null

代码实现

C# 实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode InsertionSortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode lastSorted = head;
        ListNode curr = head.next;
        
        while (curr != null) {
            if (lastSorted.val <= curr.val) {
                lastSorted = lastSorted.next;
            } else {
                ListNode prev = dummy;
                while (prev.next.val <= curr.val) {
                    prev = prev.next;
                }
                lastSorted.next = curr.next;
                curr.next = prev.next;
                prev.next = curr;
            }
            curr = lastSorted.next;
        }
        
        return dummy.next;
    }
}

Python 实现

# 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]:
        if not head or not head.next:
            return head
        
        dummy = ListNode(0)
        dummy.next = head
        last_sorted = head
        curr = head.next
        
        while curr:
            if last_sorted.val <= curr.val:
                last_sorted = last_sorted.next
            else:
                prev = dummy
                while prev.next.val <= curr.val:
                    prev = prev.next
                last_sorted.next = curr.next
                curr.next = prev.next
                prev.next = curr
            curr = last_sorted.next
        
        return dummy.next

C++ 实现

/**
 * 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) {
        if (!head || !head->next) {
            return head;
        }
        
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* lastSorted = head;
        ListNode* curr = head->next;
        
        while (curr) {
            if (lastSorted->val <= curr->val) {
                lastSorted = lastSorted->next;
            } else {
                ListNode* prev = dummy;
                while (prev->next->val <= curr->val) {
                    prev = prev->next;
                }
                lastSorted->next = curr->next;
                curr->next = prev->next;
                prev->next = curr;
            }
            curr = lastSorted->next;
        }
        
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

性能分析

各语言的性能对比：

实现语言	执行用时	内存消耗
C++	24 ms	9.6 MB
C#	92 ms	38.2 MB
Python	156 ms	16.8 MB

C++性能最好。插入排序时间复杂度是O(n²)，所以链表较长时会比较慢。

补充说明

代码亮点

1. 用哑节点简化头节点的插入操作
2. 通过维护lastSorted节点优化性能（已经排好序的部分不用再遍历）
3. 处理了边界情况

常见错误

1. 忘记用哑节点，导致头节点插入很复杂
2. 没有正确维护lastSorted指针
3. 链表操作时指针更新顺序错了

相关题目

• 148. 排序链表
• 21. 合并两个有序链表
• 23. 合并K个升序链表

讨论

有几个问题可以思考一下：

1. 插入排序的时间复杂度是O(n²)，为什么还要学这道题？有没有更快的排序方法？
2. 哑节点（dummy node）在链表题中很常用，你还见过哪些题用到了这个技巧？
3. 这道题的优化（判断是否需要插入）在什么情况下效果最好？

欢迎在评论区讨论。

---

如果你都看到这里了，说明还是有点收获的吧？给个赞鼓励一下呗。