描述

现有一链表的头指针 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;}
};