链表
解题思路
复杂度
-
时间复杂度：
O(n^2)，其中 n 是链表的长度； -
空间复杂度：
O(1)
代码实现
var insertionSortList = function (head) {
if (!head) return head;
// 1. 定义一个排序链表
let dummyHead = new ListNode(0, null);
let cur = head;
let pre = dummyHead;
while (cur) {
// 2. 找到 cur 在排序链表中的位置，后面进行插入操作
while (pre.next && pre.next.val < cur.val) {
pre = pre.next;
}
// 3. 将 head 插入到排序链表中
let next = cur.next; // 步骤一：保存 cur.next
cur.next = pre.next; // 步骤二
pre.next = cur; // 步骤三
pre = dummyHead; // 步骤四：pre 重新指向虚拟头结点来找下一个插入位置
cur = next; // 步骤五：cur 的前一个节点的下一个节点指向保存的 next
}
return dummyHead.next;
}
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 1305. 两棵二叉搜索树中的所有元素
上一篇
评论
