【算法--链表】86.分割链表--通俗讲解
一、题目是啥？一句话说清
给你一个链表和一个值 x，把链表分成两部分：所有小于 x 的节点都放在大于或等于 x 的节点之前，并且保持节点原来的相对顺序。
示例：
- 输入：head = [1,4,3,2,5,2], x = 3
- 输出：[1,2,2,4,3,5]（所有小于3的节点1、2、2都在大于等于3的节点4、3、5之前，且相对顺序不变）
二、解题核心
使用两个临时链表：一个收集所有小于 x 的节点，另一个收集所有大于或等于 x 的节点。遍历原链表，将每个节点分配到对应的临时链表中，最后将两个临时链表连接起来。 这就像把一堆水果分成两筐：一筐放所有苹果，另一筐放所有橙子，然后把苹果筐放在橙子筐前面。
三、关键在哪里？（3个核心点）
想理解并解决这道题，必须抓住以下三个关键点：
1. 两个临时链表的使用
- 是什么：创建两个临时链表，分别存储小于 x 的节点和大于等于 x 的节点。
- 为什么重要：这样可以保持节点的相对顺序，因为节点被按顺序添加到对应的链表中。
2. 哑节点（Dummy Node）的运用
- 是什么：为每个临时链表创建一个哑节点作为头节点，简化链表操作。
- 为什么重要：哑节点可以避免处理空链表的边界情况，让代码更简洁。
3. 正确连接链表
- 是什么：遍历完成后，将小于 x 的链表的末尾指向大于等于 x 的链表的头节点，并将大于等于 x 的链表的末尾指向 null。
- 为什么重要：如果连接不正确，可能会导致链表断开或形成环。
四、看图理解流程（通俗理解版本）
让我们用链表 1 → 4 → 3 → 2 → 5 → 2 和 x=3 的例子来可视化过程：
-
初始化：
- 创建两个哑节点：leftDummy 和 rightDummy。
- 初始化两个指针 left 和 right，分别指向 leftDummy 和 rightDummy。
- 初始状态：leftDummy → null, rightDummy → null
-
遍历原链表：
- 节点1：值1 < 3，添加到 left 链表：leftDummy → 1
- 节点4：值4 ≥ 3，添加到 right 链表：rightDummy → 4
- 节点3：值3 ≥ 3，添加到 right 链表：rightDummy → 4 → 3
- 节点2：值2 < 3，添加到 left 链表：leftDummy → 1 → 2
- 节点5：值5 ≥ 3，添加到 right 链表：rightDummy → 4 → 3 → 5
- 节点2：值2 < 3，添加到 left 链表：leftDummy → 1 → 2 → 2
-
连接链表：
- 将 left 链表的末尾（最后一个2）指向 right 链表的头节点（4）。
- 将 right 链表的末尾（5）指向 null。
- 最终链表：leftDummy → 1 → 2 → 2 → 4 → 3 → 5
-
返回结果：返回 leftDummy.next，即节点1。
五、C++ 代码实现（附详细注释）
#include <iostream>
using namespace std;// 链表节点定义
struct ListNode {int val