链表分割
文章目录
- 链表分割
-
- 一、题目
- 二、思路分析
一、题目
?题目指路：CM11 链表分割_牛客题霸_牛客网 (nowcoder.com)
??现有一链表的头指针ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针
二、思路分析
?错误思路：
遍历两遍链表，第一次找小的数，第二次找大的数，但存在隐患，因为链表是连在一起的，将前面节点放到新的链表中，链表中的结构会紊乱
?普通思路：
新定义一个哨兵的头节点，大于x的尾插，小于x的头插
结果：
可以看到方法是好方法，但是最后的结果顺序不对
我们任然需要切换思路
?巧妙思路：
??链表和数组不同，链表在链表的节点之间做手脚是不占用内存，
??新建链表的节点去重新构建链表，只要把哨兵头节点free掉，就不存在占用空间
??既然要我们找比x小和比x大的数，分别放在两头，那么在第二种思路的基础上，我们不用同一个链表，因为可以看到中间的哨兵头节点还需要一个指针去存储它的地址
??而且我们需要的都是尾插，因为尾插顺序不会改变
??两个链表，一个存储比x小，一个存储比x大，最后再将链表链接起来
?准备好需要的哨兵节点，以及尾插需要的双指针
?因为这里不需要走回头路，直接插入就行，上面的next指针可以省略
?以 x = 3为例
?模拟第一步：
?模拟第二步：
?模拟第三步
??注意这里greaterhead和lesstail的下一个都指向4??
?模拟第四步
?模拟第五步
??这里最后greatertail还连着lesstail，所以最后要把它们next都为NULL??
??最后变成：
??代码如下：
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {if(pHead == NULL){return NULL;}ListNode* cur = pHead;ListNode* lesshead = (ListNode*)malloc(sizeof(ListNode));ListNode* greaterhead = (ListNode*)malloc(sizeof(ListNode));ListNode* lesstail = lesshead;ListNode* greatertail = greaterhead;while(cur){if(cur->val < x){lesstail->next = cur;lesstail = cur;cur = cur->next;}else{greatertail->next = cur;greatertail = cur;cur = cur->next;}}greatertail->next = NULL;lesstail->next = greaterhead->next;ListNode* ret = lesshead->next;free(greaterhead);free(lesshead);return ret;}
};