链表OJ题(六)

1. 链表分割

链接：CM11 链表分割

描述：
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

思路一带哨兵位的头结点

题目要求我们将小于 x 的节点和大于等于 x 的节点分隔，小于 x 的节点在前，大于等于 x 的节点在后，且不能改变原来的数据顺序。

不能改变顺序就比较棘手，如果没有这个条件，我们可以用双指针来写。但是题目既然给出了要求，我们就得想办法解决。

我们创建一个新链表存放小于 x 的值，另一个存放大于等于 x 的值。然后遍历原链表，将符合条件的值放入对应的链表中，最后再将存放小于 x 的值的链表和存放大于等于 x 的值的链表链接起来。

那么这过程肯定是尾插，本题使用哨兵位是十分合适的，因为本题有很多的空指针处理的情况，所以我们设定两个哨兵位 lessHead 、 greaterHead。

再给定两个尾lessTail 、 greaterTail，用来尾插。但是最后记得释放哨兵位。

注意如果以 greaterHead 结束的元素不是链表的最后一个元素(即原链表最后一个元素小于 x )，就可能会造成 链表带环 的情况,因为尾插改变前一个链接关系，没有改变自己的后一个链接关系，所以需要断开环，然后将 greaterTail 的 next 置为空。
在这里插入图片描述

代码：


class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessTail, *lessHead, *greaterTail, *greaterHead;// 建立哨兵位lessTail = lessHead = (struct ListNode*)malloc(sizeof(struct ListNode));greaterTail = greaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* cur = pHead;while (cur){if (cur->val < x){lessTail->next = cur;lessTail = cur;}else{greaterTail->next = cur;greaterTail = cur;}cur = cur->next;}// 链接两个链表lessTail->next = greaterHead->next;greaterTail->next = NULL; // 断开环// 拷贝节点，释放哨兵位struct ListNode* ans = lessHead->next;free(lessHead);free(greaterHead);return ans;}
};

在这里插入图片描述

思路二不强行加头结点

这道题目不用哨兵位也可以做，但是比较考验细节

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {struct ListNode* lessTail, *lessHead, *greaterHead, *greaterTail;lessTail = lessHead = greaterHead = greaterTail = NULL;struct ListNode* cur = pHead;while (cur){if (cur->val < x){if (lessTail == NULL){// 第一次尾插lessHead = lessTail = cur;}else{lessTail->next = cur;lessTail = lessTail->next;}cur = cur->next;}else{if (greaterTail == NULL){// 第一次尾插greaterHead = greaterTail = cur;}else{greaterTail->next = cur;greaterTail = greaterTail->next;}cur = cur->next;}}// lessHead 为空，说明原链表为空或链表的值全大于 x// 且链表尾部的 next 一定为空// 返回 greaterHeadif (lessHead == NULL)return greaterHead;// 如果 lessHead 和 greaterHead 都不为空// 说明正常分割// 将其链接，greaterHead 尾部链空if (lessHead != NULL && greaterHead != NULL){lessTail->next = greaterHead;greaterTail->next = NULL;}// 无论是正常分割，还是链表的值全小于 x// 都是返回 lessHeadreturn lessHead;}
};