前言
本系列主要讲解链表的经典题
注：划重点！！必考~
链表分割
- 题目描述：
现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
- 解题思路：
- 因为需要相对顺序不变，所以我们选择用尾插法
- 要将小的放在前面，打的放在后面，这里我们可以选择使用两个链表
- 一个链接小的结点，另一个链接大的结点，最后再将大的链表尾插到小的链表上
- 参考代码：
/* 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; } };
结果：
