86.分隔链表
86. 分隔链表
题意
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的
节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。
难度
中等
示例
示例 1：
086.%E5%88%86%E9%9A%94%E9%93%BE%E8%A1%A8-20231004090206.png
输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]
示例 2：
输入：head = [2,1], x = 2
输出：[1,2]
分析
本题考察的是对链表的遍历和基础操作。
思路其实很简单，遍历一遍链表，然后按照节点元素的大小，将其分别存储到两个链表
中，最后再将较大的链表链接到较小的链表，即可完成本题。
题目的难点主要集中在链表的操作上，有时我们常常会被链表的一些基础操作绕晕，要不
被绕晕，就要对链表这一基础数据结构烂熟于心。
因为要用两个头节点存放链表的较小元素和较大元素，同时为了防止其中任一链表为空，
我们可以这样来实现。
利用 smallListHead 和 largeListHead 两个头节点来存储两个链表，然后遍历链表，按
照节点大小将节点插入两个链表即可。
最后，记得将存储较大元素的链表尾节点的 next 设置为 null，因为这时的尾节点不一定
是原先链表的尾节点，可能会导致我们的最终答案还多出一节。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
*}
*/
class Solution {
public ListNode partition(ListNode head, int x) {
// 创建两个新链表，一个用于存放小于 x 的节点，另一个用于存放大于等于 x 的节点
ListNode beforeHead = new ListNode(0), before = beforeHead; // 小于 x
ListNode afterHead = new ListNode(0), after = afterHead; // 大于等于 x
while (head != null) {
if (head.val < x) {
before.next = head;
before = before.next;
} else {
after.next = head;
after = after.next;
}
head = head.next;
}
after.next = null; // 终止大于等于 x 的链表
before.next = afterHead.next; // 连接两个链表
return beforeHead.next; // 返回分割后的链表
}
}
我们来模拟一下整个过程。假设我们有以下链表和分隔值：
链表: 1 -> 4 -> 3 -> 2 -> 5 -> 2
x: 3
步骤 1: 初始化两个临时头节点，beforeHead 和 afterHead。
beforeHead -> [empty list]
afterHead -> [empty list]
步骤 2: 开始遍历链表，根据每个节点的值和 x 的关系，将其添加到对应的临时链表中。
• 对于值 1，因为它小于 3，我们将其添加到 before 链表。
beforeHead -> 1
afterHead -> [empty list]
• 对于值 4，因为它大于 3，我们将其添加到 after 链表。
beforeHead -> 1
afterHead -> 4
• 对于值 3，它等于 x，所以也加入 after 链表。
beforeHead -> 1
afterHead -> 4 -> 3
• 对于值 2 (第一个)，因为它小于 3，我们将其添加到 before 链表。
beforeHead -> 1 -> 2
afterHead -> 4 -> 3
• 同样，对于值 5 和值 2 (第二个) 的处理，我们得到：
beforeHead -> 1 -> 2 -> 2
afterHead -> 4 -> 3 -> 5
步骤 3: 将 before 链表的尾部连接到 after 链表的头部。
beforeHead -> 1 -> 2 -> 2 -> 4 -> 3 -> 5
这就是我们想要的结果。
时间复杂度为 (O(n))，其中 (n) 是链表的长度，空间复杂度为 (O(1))，因为我们只是重新
排列了链表的节点，没有使用额外的空间来存储数据。
086.%E5%88%86%E9%9A%94%E9%93%BE%E8%A1%A8-20231007155200.png
总结
链表作为最基础的，也是大多数小伙伴最早接触的数据结构，必须要烂熟于心。
力扣链接：https://leetcode.cn/problems/partition-list/