描述

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater

than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example, Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.


partition_list.h

#include<iostream>#include<assert.h>#include<stdlib.h>usingnamespacestd;typedefstructListNode{int_val;ListNode*_next;ListNode(intx):_val(x),_next(NULL){}}node,*node_p;classSolution{public:node_ppartition(node_p&list,intx){//参数检查if(list==NULL)returnNULL;nodedummy(-1);node_phead=&dummy;head->_next=list;node_pfirst=head;//找_val为x的结点node_pnode_x=list;while(node_x!=NULL&&node_x->_val!=x){node_x=node_x->_next;first=first->_next;}if(node_x==NULL){cout<<"notfindnode_x!"<<endl;returnlist;}node_pprev=node_x;node_ptmp=node_x->_next;while(tmp){if(tmp->_val<x){prev->_next=tmp->_next;tmp->_next=node_x;first->_next=tmp;first=first->_next;tmp=node_x->_next;}else{tmp=tmp->_next;prev=prev->_next;}}returnhead->_next;}//构造一个链表node_pcreate_list(int*array,intsize){assert(array);nodedummy(-1);node_pprev=&dummy;node_phead=prev;for(inti=0;i<size;++i){node_pNode=newnode(array[i]);prev->_next=Node;prev=prev->_next;}returnhead->_next;}};

partition_list.cpp

#include"partition_list.h"usingnamespacestd;intmain(){intarray[]={1,4,3,2,5,2};Solutions1;node_plist=s1.create_list(array,sizeof(array)/sizeof(array[0]));node_pnewlist=s1.partition(list,4);node_ptmp=newlist;while(tmp){cout<<tmp->_val<<"";free(tmp);tmp=tmp->_next;}cout<<endl;return0;}

运行结果：


下面为leetcode实现的代码：



《完》