链表分割_牛客题霸_牛客网
1 题目描述
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
如上链表，x等于4，则需要将小于4的结点放到左边，且不改变其本身的相对顺序，即变成3>>2>>1。将大于4的放到右边，不改变相对顺序，即5>>6>>7。
所以最后得到的新链表为3>>2>>1>>5>>6>>7。
2 解题思路
通过给出的分割点，将链表分割为左右两个链表，即大于4的放一边，小于4的放一边，等于4的结点随便放哪一边都行。最后再把前后两个链表再串起来。
cur为遍历原链表指针，用两个新的头结点去尾插合法满足条件的结点。
最后将两个链表串起来。
3 完整代码
/*
struct ListNode {int val;struct ListNode *next;ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:ListNode* partition(ListNode* pHead, int x) {ListNode *cur=pHead;ListNode *list1,*list1tail;ListNode *list2,*list2tail;list1=list1tail=(ListNode*)malloc(sizeof(ListNode));list2=list2tail=(ListNode*)malloc(sizeof(ListNode));list1->next=list1tail->next=NULL;list2->next=list2tail->next=NULL;while(cur){if(cur->val<x){list1tail->next=cur;list1tail=cur;}else {{list2tail->next=cur;list2tail=cur;}}cur=cur->next;}list1tail->next=list2->next;free(list2);list2tail->next=NULL;ListNode *head=list1->next;free(list1);return head;}
};
