Given a linked list and a value x, partition it such that all nodes less thanx 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.

/**
 * 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) {
        ListNode *smallhead = NULL;
	ListNode *bighead = NULL;
	ListNode *tail_small = NULL;
	ListNode *tail_big = NULL;
	ListNode *cur = head;
	if (head == NULL || head->next == NULL)
	{
		return head;
	}
	while(cur != NULL)
	{
		ListNode *tmp_next = cur->next;
		if (cur->val < x)
		{
			if (smallhead == NULL)
			{
				smallhead = tail_small = cur;
			}
			else {
				tail_small->next = cur;
				tail_small = cur;
			}
		}
		else{
			if (bighead == NULL)
			{
				bighead = tail_big = cur;
			}
			else{
				tail_big->next = cur;
				tail_big = cur;
			}
		}
		cur = tmp_next;
	}
	if (tail_small == NULL)
	{
		tail_big->next = NULL;
		return bighead;
	}
	if (tail_big == NULL)
	{
		tail_small->next = NULL;
		return smallhead;
	}
	tail_small->next = bighead;
	tail_big->next = NULL;
	return smallhead;
    }
};