前言
本系列主要讲解链表的经典题 注:划重点!!必考~
链表分割
现有一链表的头指针 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;
}
};