### leetcode Question 63: Partition List

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 tox.
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.

Analysis:
Simple idea but be careful with the operation of pointers.
The idea is:   first get the last element and the length of the list (1 while loop)
Then scan the whole list, if current node value < x, then go to the next node.
if current node value >=x, then move this node to the end of the list.
until  meet the length of the original list.

Code:
/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *partition(ListNode *head, int x) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
ListNode *p= new ListNode(0);
head = p; // used to save the result head.
ListNode *last=head; // used to get the last node

int n=0; //length of the list
while (last->next!=NULL){ last=last->next; n++; } //get the length and last node

while (n>0){  // in case  of non-stop loop, count n.
if (p->next->val < x){  // val<x keep the node
p=p->next;
n--;
}else{                  // val>=x move to last
last->next = new ListNode(p->next->val);    // add node to the last
last = last->next;
p->next = p->next->next;                    //delete current node
n--;
}
}
return head->next;  //the 1st node is elmininated
}
};


1. Hi Yu,
I find your solutions very lucid and easy to understand. When I try to solve these questions on my own, I am unable to do so. But when I look at your solutions, it seems so easy. Could you please guide me as to how to approach problems. Thanks in advance :)

2. 1. Remove elements that are greater than or equal to X
2. Keep track of removed items in a separate linked list
3. When the scan is complete, append the removed items to the end of the original list

3. Isn't there a memory leak at this line p->next = p->next->next; //delete current node