【牛客CM11】链表分割
刷爆LeetCode系列
牛客CM11：
github地址
前言
本文用C++实现牛客CM11题
题目描述
题目与思路分析
目标分析：
- 编写代码，给定链表的头指针
pHead，以给定值x为基准，将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 - 不能改变原来数据的顺序
- 返回分割后的新链表的头指针
- 要求：时间复杂度为
O(n)，空间复杂度为O(1)
思路：创建两个哨兵位的头结点guardLess 和 guardGreater，遍历链表，小于 x 的结点尾插到 guardLess，大于 x 的结点尾插到 guardGreater，最终再将两个链表连接起来，尾插的时候注意记录tail结点
操作：
- 空链表检查：
if (pHead == nullptr) return nullptr; - 创建两个哨兵位的头结点：
ListNode* guardLess =newListNode(-1); ListNode* guardGreater =newListNode(-1);- 分别创建两个链表的尾结点，方便尾插时无需频繁找尾：
ListNode* lessTail = guardLess,*greaterTail = guardGreater - curNode为移动指针，用于遍历链表：
- 小于 x 的结点尾插到
guardLess链表中，同时尾指针lessTail向后移动 - 大于等于 x 的结点尾插到
guardGreater链表中，同时尾指针greaterTail向后移动 - 每次循环中curNode指针向后移动：
curNode = curNode->next
- 小于 x 的结点尾插到
- 连接两个新链表：
lessTail->next = guardGreater->next - 最后一个结点的 next 指针需要置空，防止链表带环：
greaterTail->next = nullptr - 保存新链表的头结点：
pHead = guardLess->next - 释放手动开辟的哨兵位头结点：
- 最终返回新链表的头结点：
return pHead
delete guardGreater;delete guardLess;代码实现
classPartition{public: ListNode*partition(ListNode* pHead,int x){if(pHead ==nullptr)returnnullptr; ListNode* guardLess =newListNode(-1); ListNode* guardGreater =newListNode(-1); ListNode* lessTail = guardLess,*greaterTail = guardGreater; ListNode* curNode = pHead;while(curNode){if(curNode->val < x){ lessTail->next = curNode; lessTail = lessTail->next;}else{ greaterTail->next = curNode; greaterTail = greaterTail->next;} curNode = curNode->next;}// 链接两个链表 lessTail->next = guardGreater->next;// 最后一个结点的 next 指针需要置空，防止链表带环 greaterTail->next =nullptr;// 释放哨兵位的头结点 pHead = guardLess->next;delete guardGreater;delete guardLess;return pHead;}};算法代码优化
- 以上代码和思路已足够精简，无需优化
以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步
分享到此结束啦你的每一次互动，都是对作者最大的鼓励！
一键三连，好运连连！征程尚未结束，让我们在广阔的世界里继续前行！🚀
