LeetCode 题解工作台
对链表进行插入排序
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。 插入排序 算法的步骤: 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。 重复直到所…
2
题型
4
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
class Solution: def insertionSortList(self, head: ListNode) -> ListNode:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。
插入排序 算法的步骤:
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。
示例 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
解题思路
方法一
# 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: ListNode) -> ListNode:
if head is None or head.next is None:
return head
dummy = ListNode(head.val, head)
pre, cur = dummy, head
while cur:
if pre.val <= cur.val:
pre, cur = cur, cur.next
continue
p = dummy
while p.next.val <= cur.val:
p = p.next
t = cur.next
cur.next = p.next
p.next = cur
pre.next = t
cur = t
return dummy.next
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N^2) because each node may require scanning the sorted portion to find its position. Space complexity is O(1) since all operations are done by reassigning existing pointers without allocating additional storage. |
| 空间 | \mathcal{O}(1) |
面试官常问的追问
外企场景- question_mark
Asks about pointer manipulation and edge cases when inserting at head.
- question_mark
Checks if you can maintain O(1) space while performing insertions.
- question_mark
May present a partially sorted list to observe iterative insertion handling.
常见陷阱
外企场景- error
Forgetting to update the next pointer before insertion, leading to lost nodes.
- error
Incorrect handling when inserting a node before the head of the sorted list.
- error
Confusing consecutive nodes, which can result in incorrect ordering or infinite loops.
进阶变体
外企场景- arrow_right_alt
Sorting a doubly linked list using insertion sort with similar pointer updates.
- arrow_right_alt
Implementing insertion sort recursively on a linked list.
- arrow_right_alt
Optimizing by reducing redundant traversal when inserting consecutive nodes already in order.