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.

Solution :
The list can be traveled once to get the count of nodes and place a pointer at the last node.
In the next step, the  list is traveled again from head, and each node having value greater than x is placed at the end of the list.

Code :

	class Solution {
	public:
	ListNode *partition(ListNode *head, int x) {
	if(head==NULL || head->next==NULL) return head;
	int n=0;
	ListNode *p = new ListNode(0);
	p->next=head;
	head = p;
	ListNode *last = p;
	while(last->next!=NULL) {last=last->next;n++;}
	while(n>0){
	if(p->next->val<x){
	p=p->next;
	n--;
	}
	else{
	last->next = new ListNode(p->next->val);
	last=last->next;
	p->next=p->next->next;
	n--;
	}
	}
	return head->next;
	}
	};

view raw PartitionList hosted with ❤ by GitHub

Please comment to suggest a better method.