LeetCode Q86: Partition List

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.

	ListNode* partition(ListNode* head, int x) {
	if(head==NULL)
	return head;
	ListNode* less=NULL;
	ListNode* greater=NULL;
	ListNode* cur=head;
	ListNode* greaterHead=NULL;
	while(cur!=NULL){
	if(cur->val<x){
	if(less==NULL){
	less=cur;
	head=cur;
	}
	else{
	less->next=cur;
	less=cur;
	}
	cur=cur->next==NULL? NULL:cur->next;
	}else{
	if(greater==NULL){
	greater=cur;
	greaterHead=cur;
	}else{
	greater->next=cur;
	greater=cur;
	}
	cur=cur->next==NULL? NULL:cur->next;
	}
	}
	if(greater!=NULL)
	greater->next=NULL;
	if(less!=NULL)
	less->next=greaterHead;
	return head;
	}

view raw Q86PartitionList.cpp hosted with ❤ by GitHub