【初阶数据结构题目】9. 链表分割

链表分割

点击链接做题

例如：

排序前：1->6->2->3->5

X：X = 3

排序后：1->2->6->3->5

思路：

排序前：1->6->2->3->5

小链表：malloc->1->2

大链表：malloc->6->3->5

最后：1->2->6->3->5(把2的next指向6)

思路代码：

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code here//创建两个非空链表ListNode* lessHead, *lessTail;lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));ListNode* greaterHead, *greaterTail;greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));//遍历链表，找小于x的和其他节点尾插到大小链表中ListNode* pcur = pHead;while(pcur){//等价于pcur!=NULLif(pcur->val < x){//尾插到小链表lessTail->next = pcur;lessTail = lessTail->next;}else{//尾插到大链表greaterTail->next = pcur;greaterTail = greaterTail->next;}pcur = pcur->next;}//大小链表首尾相连lessTail->next = greaterHead->next;ListNode* ret = lessHead->next;free(lessHead);free(greaterHead);lessHead = greaterHead = NULL;return ret;}
};

上面这个代码提示内存超限，因为有个问题：

例如：

排序前：5->1->3->6->2

小链表：malloc->1->2

大链表：malloc->5->3->6

结果：1->2->5->3->6->2->5->3->6

（因为这里是把2的next指向5，来让两个链表连起来。但是6的next我们没有改，在排序前6的next是2，所以这里会死循环）

我们只要将大链表的尾结点的next指针置为null就可以了

/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {// write code here//创建两个非空链表ListNode* lessHead, *lessTail;lessHead = lessTail = (ListNode*)malloc(sizeof(ListNode));ListNode* greaterHead, *greaterTail;greaterHead = greaterTail = (ListNode*)malloc(sizeof(ListNode));//遍历链表，找小于x的和其他节点尾插到大小链表中ListNode* pcur = pHead;while(pcur){//等价于pcur!=NULLif(pcur->val < x){//尾插到小链表lessTail->next = pcur;lessTail = lessTail->next;}else{//尾插到大链表greaterTail->next = pcur;greaterTail = greaterTail->next;}pcur = pcur->next;}//将大链表的尾结点的next指针置为nullgreaterTail->next = NULL;//大小链表首尾相连lessTail->next = greaterHead->next;ListNode* ret = lessHead->next;free(lessHead);free(greaterHead);lessHead = greaterHead = NULL;return ret;}
};