66.分隔链表
题目
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
示例 1：
- 输入：head = [1,4,3,2,5,2], x = 3
- 输出：[1,2,2,4,3,5]
说明：小于 3 的节点是 1、2、2（按原顺序）；大于等于 3 的是 4、3、5（按原顺序）； 把前者拼在后者前面。
示例 2：
- 输入：head = [2,1], x = 2
- 输出：[1,2]
提示：
- 链表中节点的数目在范围 [0, 200] 内
- -100 <= Node.val <= 100
- -200 <= x <= 200
思路
分成两队，最后合并
这道题的思路特别直白，就像排队分流:
想象成一个门口有个安检，你手里拿着标准值x。链表里的节点排着队一个一个过来:
- 值小于x的节点，让它排到小队里。
- 值大于等于x的节点，让它排到大队里。
因为我们是按照原链表顺序依次处理每个节点的，所以每个分区内部自然就保持了原来的相对顺序(先来的先排，后来的后排)。
最后，把小队的尾巴接上大队的头，两队拼成一条链，就是答案。
原链表: 1 -> 4 -> 3 -> 2 -> 5 -> 2 x = 3
分流:
- 小队(<3): 1 -> 2 -> 2
- 大队(>=3): 4 -> 3 -> 5
- 合并: 1 -> 2 -> 2 -> 4 -> 3 -> 5
两个dummy: 给两条新链各配一个头
我们要新建两条链表(小队和大队)，但一开始它们都是空的，没有头节点，往里加节点时会很麻烦(需要判断是不是第一个节点)。
老办法: 给每条链都配一个dummy哨兵节点:
- smallDummy: 小队的虚拟头，配一个移动指针samll负责往小队尾部接节点
- largeDummy: 大队的虚拟头，配一个移动指针large负责往大队尾部接节点
class ListNode(var `val`: Int) {
var next: ListNode? = null
}
class Solution {
fun partition(head: ListNode?, x: Int): ListNode? {
// 1. 两个哨兵节点，分别作为"小队"和"大队"的虚拟头
val smallDummy = ListNode(0)
val largeDummy = ListNode(0)
// small / large 是两条链的尾指针，负责往各自队尾追加节点
var small: ListNode = smallDummy
var large: ListNode = largeDummy
// 2. 遍历原链表，把每个节点按值分流到两条链中
var cur = head
while (cur != null) {
if (cur.`val` < x) {
small.next = cur // 接到小队尾部
small = cur // 更新小队尾指针
} else {
large.next = cur // 接到大队尾部
large = cur // 更新大队尾指针
}
cur = cur.next
}
// 3. 收尾一：大队尾部置空，切断原链表残留的指向，防止成环
large.next = null
// 4. 收尾二：小队尾部接上大队的头，拼成完整链表
small.next = largeDummy.next
// 5. 返回小队的真正头节点
return smallDummy.next
}
}
复杂度
- 时间复杂度: O(n)：只遍历一遍原链表，每个节点处理一次。
- 空间复杂度: O(1)：只用了两个 dummy 和几个指针，没有开辟和节点数成正比的额外空间（节点是复用原链表的，没有新建）。
- 邮箱 ：charon.chui@gmail.com
- Good Luck!