1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| func insertionSortList(head *ListNode) *ListNode {
dummy := &ListNode{}
cur := head
for cur != nil {
// 在每一次迭代中，我们要插入的节点是 cur
// 需要从已排序部分的头节点开始寻找插入位置
pre := dummy
nextNode := pre.Next
// 寻找插入位置，找到第一个大于等于当前节点值的节点
for nextNode != nil && nextNode.Val < cur.Val {
pre = nextNode
nextNode = nextNode.Next
}
// 插入当前节点到已排序部分的合适位置
temp := cur.Next // 保存未排序部分的下一个节点
cur.Next = nextNode // 将当前节点连接到已排序部分
pre.Next = cur // 将当前节点插入到已排序部分
cur = temp // 将当前节点移动到下一个未排序节点
}
return dummy.Next // 返回已排序部分的头节点
}
|