前言

本系列主要讲解链表的经典题

注：划重点！！必考~

链表分割

牛客链接：链表分割_牛客题霸_牛客网 (nowcoder.com)

• 题目描述：

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

• 解题思路：

1. 因为需要相对顺序不变，所以我们选择用尾插法
2. 要将小的放在前面，打的放在后面，这里我们可以选择使用两个链表
3. 一个链接小的结点，另一个链接大的结点，最后再将大的链表尾插到小的链表上

• 参考代码：

/*
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*longhead=(struct ListNode*)malloc(sizeof(struct ListNode));longhead->next=NULL;struct ListNode*lesshead=(struct ListNode*)malloc(sizeof(struct ListNode));lesshead->next=NULL;//创建寻址指针struct ListNode*cur1=pHead,*cur2=longhead,*cur3=lesshead;while(cur1){//根据节点数据大小决定接上的链表的位置if(cur1->val<x){cur3->next=cur1;cur3=cur1;}else{cur2->next=cur1;cur2=cur1;}//找下一个节点cur1=cur1->next;}//尾节点置空，避免成环cur2->next=NULL;//两个链表接成一条cur3->next=longhead->next;//记录头结点位置struct ListNode*next=lesshead->next;//释放哨兵卫free(longhead);free(lesshead);return next;}
};

• 结果：