算法题题解：分隔链表

Problem: 86. 分隔 链表

题目描述：

给定一个链表和一个值 x，要求将链表重新排列，所有小于 x 的节点放在前面，所有大于或等于 x 的节点放在后面。要求保留节点的相对顺序。

解题思路：

因为是链表而不是数组，构建子链不增加空间复杂度。勇敢地构造子链即可，无需考虑节点交换。

我们可以通过创建两个链表来分别存储小于 x 和大于等于 x 的节点，并最终将这两个链表连接起来。这种方法可以保证在一次遍历链表的过程中完成分割操作。

具体步骤如下：

虚拟头节点：使用两个虚拟头节点，一个用于保存小于 x 的节点链表，另一个用于保存大于等于 x 的节点链表。虚拟头节点可以简化链表操作，避免处理头节点的特殊情况。
遍历链表：通过遍历原始链表，遇到小于 x 的节点，放入小于 x 的链表；遇到大于或等于 x 的节点，放入大于等于 x 的链表。
连接链表：遍历完成后，将两个链表连接起来，并确保大于等于 x 的链表末尾指向 NULL，防止形成环。
返回新链表头：最后返回重新排列后的链表头部。

解题过程：

定义虚拟头节点：使用 lowDummy 和 highDummy 作为小于 x 和大于等于 x 的链表的虚拟头节点。
遍历链表：我们通过遍历原始链表，将每个节点根据其值加入对应的链表（low 或 high）。
处理边界情况：遍历结束后，确保大于等于 x 的链表以 NULL 结尾。
连接两个链表：将小于 x 的链表的末尾与大于等于 x 的链表的头部连接起来。

代码实现：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* partition(struct ListNode* head, int x) {
    // 定义两个虚拟头节点，分别用于存放小于x的和大于等于x的节点
    struct ListNode lowDummy, highDummy;
    
    // 初始化两个指针用于遍历链表并构建两个链表
    struct ListNode *low = &lowDummy, *high = &highDummy;
    struct ListNode *p = head;
    
    // 初始化虚拟头节点的next指针为空，防止产生垃圾数据
    lowDummy.next = NULL;
    highDummy.next = NULL;
    
    // 遍历原链表并进行分割
    while (p) {
        if (p->val < x) {
            low->next = p;  // 将当前节点加入到小于x的链表中
            low = low->next;
        } else {
            high->next = p;  // 将当前节点加入到大于等于x的链表中
            high = high->next;
        }
        p = p->next;  // 移动到下一个节点
    }

    // 终止大于等于x的链表，防止形成环
    high->next = NULL;
    
    // 将小于x的链表与大于等于x的链表连接起来
    low->next = highDummy.next;

    // 返回小于x的链表头部
    return lowDummy.next;
}