链表分割算法实现：以给定值 x 为基准

题目描述

题目链接：牛客网 CM11

题目与思路分析

目标分析：

1. 编写代码，给定链表的头指针 pHead，以给定值 x 为基准，将链表分割成两部分，所有小于 x 的结点排在大于或等于 x 的结点之前。
2. 不能改变原来数据的顺序。
3. 返回分割后的新链表的头指针。
4. 要求：时间复杂度为 O(n)，空间复杂度为 O(1)。

思路：创建两个哨兵位的头结点 guardLess 和 guardGreater，遍历链表，小于 x 的结点尾插到 guardLess，大于 x 的结点尾插到 guardGreater，最终再将两个链表连接起来。尾插的时候注意记录 tail 结点。

操作步骤：

• 空链表检查：if (pHead == nullptr) return nullptr;
• 创建两个哨兵位的头结点：

ListNode* guardLess = new ListNode(-1);
ListNode* guardGreater = new ListNode(-1);

• 分别创建两个链表的尾结点，方便尾插时无需频繁找尾：

ListNode* lessTail = guardLess;
ListNode* greaterTail = guardGreater;

• curNode 为移动指针，用于遍历链表：
  • 小于 x 的结点尾插到 guardLess 链表中，同时尾指针 lessTail 向后移动。
  • 大于等于 x 的结点尾插到 guardGreater 链表中，同时尾指针 greaterTail 向后移动。
  • 每次循环中 curNode 指针向后移动：curNode = curNode->next。
• 连接两个新链表：lessTail->next = guardGreater->next。
• 最后一个结点的 next 指针需要置空，防止链表带环：greaterTail->next = nullptr。
• 保存新链表的头结点：pHead = guardLess->next。