牛客：链表分割算法详解

链表分割_牛客题霸_牛客网

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/#include <cstddef>
typedef struct ListNode ListNode;
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// 思路：创建两个临时链表，分别存储小于x和大于等于x的节点// 最后将两个链表连接起来// 定义两个哑头节点（简化边界处理）和对应的尾指针// lesshead/lesstail：存储所有小于x的节点// greaterhead/greatertail：存储所有大于等于x的节点ListNode *lesshead , *greaterhead;ListNode *lesstail , *greatertail;// 为哑节点分配内存lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));// 初始化哑节点的next指针为NULLlesshead->next = greaterhead->next = NULL;// 遍历原链表ListNode* cur = pHead;while(cur) {if(cur->val < x) {// 当前节点值小于x，加入到less链表lesstail->next = cur;    // 将当前节点链接到less链表尾部lesstail = lesstail->next;  // 更新less链表的尾指针} else {// 当前节点值大于等于x，加入到greater链表greatertail->next = cur;    // 将当前节点链接到greater链表尾部greatertail = greatertail->next;  // 更新greater链表的尾指针}cur = cur->next;  // 移动到下一个节点}// 将less链表的尾部与greater链表的头部连接lesstail->next = greaterhead->next;// 确保新链表的尾部为NULL，避免出现环greatertail->next = NULL;// 保存新链表的头节点（lesshead的下一个节点）ListNode* list = lesshead->next;// 释放哑节点的内存（避免内存泄漏）free(lesshead);free(greaterhead);return list;}
};/* 样例讲解：
假设输入链表为：1 -> 4 -> 3 -> 2 -> 5 -> 2，x = 3步骤1：初始化两个哑节点
lesshead(哑) -> NULL
greaterhead(哑) -> NULL步骤2：遍历原链表并分区
- 节点1（1 < 3）：加入less链表lesshead -> 1 (lesstail指向1)greaterhead -> NULL- 节点4（4 ≥ 3）：加入greater链表lesshead -> 1greaterhead -> 4 (greatertail指向4)- 节点3（3 ≥ 3）：加入greater链表lesshead -> 1greaterhead -> 4 -> 3 (greatertail指向3)- 节点2（2 < 3）：加入less链表lesshead -> 1 -> 2 (lesstail指向2)greaterhead -> 4 -> 3- 节点5（5 ≥ 3）：加入greater链表lesshead -> 1 -> 2greaterhead -> 4 -> 3 -> 5 (greatertail指向5)- 节点2（2 < 3）：加入less链表lesshead -> 1 -> 2 -> 2 (lesstail指向2)greaterhead -> 4 -> 3 -> 5步骤3：连接两个链表
less链表尾部(2) -> greater链表头部(4)
最终链表：1 -> 2 -> 2 -> 4 -> 3 -> 5步骤4：释放哑节点内存，返回结果链表
*/