# Description

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.

The original problem is here.

The original code is here.

# My Solution

I solve this problem in C++, as below:

``````/*
*Partition List
*Author: shuaijiang
*Email: zhaoshuaijiang8@gmail.com
*/
#include<iostream>
#include<queue>
#include<stdlib.h>
using namespace std;

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
queue<ListNode*> largeQueue, smallQueue;
while(node != NULL){
if(node->val >= x)
largeQueue.push(node);
else
smallQueue.push(node);
node = node->next;
}
if(!smallQueue.empty()){
smallQueue.pop();
while(!smallQueue.empty()){
node->next = smallQueue.front();
node = node->next;
smallQueue.pop();
}
}
largeQueue.pop();
}
while(!largeQueue.empty()){
node->next = largeQueue.front();
largeQueue.pop();
node = node->next;
}
node->next = NULL;