原地修改链表
解题思路
初始化哑结点 dmy 和快慢指针 fast、slow；
slow 指针向后迭代找到最后一个小于 x 的节点；
fast 从 slow 节点后寻找小于 x 的节点：
- 若找到小于 x 的节点则将该节点取出来放在 slow 后面，slow 向后移动一个位置，始终保持自己是最后一个小于 x 的节点；
- 若未找到则 fast 继续向后迭代；
返回结果 dmy.next；
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的长度； -
空间复杂度：
O(1)
代码实现
var partition = function (head, x) {
// 初始化哨兵节点 dmy.next 指向 head
let dmy = new ListNode(-1, head);
let slow = dmy;
let fast = null;
// 1.找到最后一个小于 x 的节点 赋值给 slow
while (slow !== null && slow.next !== null) {
if (slow.next.val >= x) break;
slow = slow.next;
}
// 2.fast 从 slow 向后迭代
fast = slow;
while (fast && fast.next) {
if (fast.next.val < x) {
// 2.1 遇到 fast.next.val 小于 x，将该节点 tmp 取出来，放入 slow 后面
let tmp = fast.next;
fast.next = fast.next.next;
// 将 tmp 放入 slow 后，slow 向后移动一位
tmp.next = slow.next
slow.next = tmp;
slow = slow.next;
} else {
// 2.2 遇到 fast.next.val 不小于 x，继续向后查找
fast = fast.next;
}
}
return dmy.next;
};
拆分 + 合并
解题思路
迭代链表将 小于 x 的节点依次放入到 min 链表中，将大于 x 的节点依次放入到 max 链表中；
迭代完成后，合并链表，将 max 链接到 min 的尾部；
复杂度
-
时间复杂度：
O(n)，其中 n 是链表的长度； -
空间复杂度：
O(1)
代码实现
var partition = function (head, x) {
const min = new ListNode(0, null);
const max = new ListNode(0, null);
let minDmg = min;
let maxDmg = max;
while (head) {
if (head.val < x) {
minDmg.next = head;
minDmg = minDmg.next;
} else {
maxDmg.next = head;
maxDmg = maxDmg.next;
}
head = head.next;
}
minDmg.next = max.next;
maxDmg.next = null;
return min.next;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 1373. 二叉搜索子树的最大键值和
上一篇
评论
