分隔链表：小于 x 的节点置前

## 分隔链表算法详解 ### 题目背景 本题是关于链表操作的经典问题，题目要求我们在给定一个链表的头节点 `head` 和一个特定值 `x` 的情况下，对链表进行重新排列，使得所有小于 `x` 的节点都出现在大于或等于 `x` 的节点之前，同时保持每个节点原有的相对顺序。这涉及到链表的遍历、比较以及节点的插入操作。 ### 输入与输出 - 输入参数： - `head`：一个指向链表头节点的指针，链表中的元素可以是整数，范围在 `-100 <= Node.val <= 100`。 - `x`：一个整数，用于区分节点值的大小。 - 示例1： - 链表：`head = [1, 4, 3, 2, 5, 2]` - 特定值：`x = 3` - 输出：`[1, 2, 2, 4, 3, 5]` - 示例2： - 链表：`head = [2, 1]` - 特定值：`x = 2` - 输出：`[1, 2]` ### 解决方案概述 解决这个问题的思路是使用两个辅助链表，一个 `smallHead` 用于存储所有小于 `x` 的节点，另一个 `largeHead` 用于存储大于等于 `x` 的节点。首先，我们遍历整个链表，对于每个节点： 1. 检查当前节点值 `val` 是否小于 `x`。 - 如果小于 `x`，将节点添加到 `smallHead` 链表的末尾，并更新 `small` 指针指向下一个节点。 - 如果大于等于 `x`，将节点添加到 `largeHead` 链表的末尾，并更新 `large` 指针。 2. 遍历结束后，`largeHead->next` 将是最后一个大于等于 `x` 的节点，所以将 `smallHead->next` 指向 `largeHead->next` 进行连接，这样就实现了两个链表的正确分隔。 ### 代码实现（C++） ```cpp class Solution { public: ListNode* partition(ListNode* head, int x) { ListNode* small = new ListNode(0); // 创建空小链表头 ListNode* smallHead = small; ListNode* large = new ListNode(0); // 创建空大链表头 ListNode* largeHead = large; while (head != nullptr) { // 遍历原始链表 if (head->val < x) { // 当前节点值小于 x small->next = head; small = small->next; // 更新小链表指针 } else { large->next = head; large = large->next; // 更新大链表指针 } head = head->next; } large->next = nullptr; // 大链表结束标记 small->next = largeHead->next; // 小链表连接到大链表之后 return smallHead->next; // 返回新的头节点 } }; ``` 通过这个解决方案，我们成功地将链表根据指定值 `x` 进行了分隔，同时保持了节点的相对顺序。这个过程主要涉及到了链表的基本操作，如指针的移动和节点的插入，是数据结构和算法中的一个重要应用。