数据结构:(牛客)CM11 链表分割
描述
现有一链表的头指针 ListNode* pHead,给一定值x,编写一段代码将所有小于x的结点排在其余结点之前,且不能改变原来的数据顺序,返回重新排列后的链表的头指针。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
#include <cfloat>
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
typedef struct ListNode ListNode;
//创建两个非空的链表:小链表,大链表
ListNode *lessHead, *lessTail;
lessHead=lessTail=( ListNode*)malloc(sizeof(ListNode));
ListNode*greaterHead,*greaterTail;
greaterHead=greaterTail=(ListNode*)malloc(sizeof( ListNode));
//遍历链表,找到小于x的值尾插到小链表的尾结点,反之
ListNode*pcur=pHead;
while(pcur)
{
if(pcur->val<x)
{
lessTail->next=pcur;
lessTail=lessTail->next;
}
else
{
greaterTail->next=pcur;
greaterTail=greaterTail->next;
}
pcur=pcur->next;
}
//大小链表合并
greaterTail->next=NULL;
lessTail->next=greaterHead->next;
ListNode*ret=lessHead->next;
free(lessHead);
free(greaterHead);
lessHead=greaterHead=NULL;
return ret;
}
};