文章目录
一、题目描述
现有一链表的头指针 ListNode pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
二、提供方便走读代码的图
三、题目代码
提示:注意死循环,一定要把bigTail->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) {
ListNode* smallHead=(ListNode*)malloc(sizeof( ListNode));
smallHead->next=NULL;
ListNode* bigHead=(ListNode*)malloc(sizeof( ListNode));
bigHead->next=NULL;
ListNode* cur,*bigTail,*smallTail;
cur=pHead;
smallTail=smallHead;
bigTail=bigHead;
while(cur)
{
if(cur->val<x)
{
smallTail->next=cur;
smallTail=smallTail->next;
}
else
{
bigTail->next=cur;
bigTail=bigTail->next;
}
cur=cur->next;
}
bigTail->next=NULL;
smallTail->next=bigHead->next;
ListNode* newHead=smallHead->next;
free(smallHead);
free(bigHead);
return newHead;
}
};
以上是本篇文章的全部内容,如果文章有错误或者有看不懂的地方,多和喵博主交流。互相学习互相进步。如果这篇文章对你有帮助,可以给喵博主一个关注,你们的支持是我最大的动力。
文章评论