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.

Example:

Input: head = 1->4->3->2->5->2, x = 3

Output: 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) {

         if (head == nullptr) return head;       // 链表为空，则直接返回

         // 操作原始链表的准备工作

         // 包括创建一个辅助结点指向链表的头结点

         ListNode *pHead = new ListNode(-);

         pHead->next = head;

         ListNode *pre = pHead;      // pre指向遍历到的结点的前驱结点

         ListNode *cur = head;       // cur指向遍历到的当前结点（即待处理结点）

         // 创建指向大于等于x(>= x ) 结点的链表

         // 用pNew指针指向该链表的头结点，pNew为辅助结点

         ListNode *pNew = new ListNode(-);

         ListNode *ptrNew = pNew;

         // 对原始链表进行遍历

         while (cur != nullptr)

         {

             if (cur->val >= x)    // 将原始链表中大于等于x（>= x）的结点分离出来，形成新的链表

             {

                 ListNode *pTemp = cur;

                 pre->next = pTemp->next;

                 cur = cur->next;

                 ptrNew->next = pTemp;

                 ptrNew = ptrNew->next;

                 ptrNew->next = nullptr;

             }

             else    // 对于原始链表中小于x(< x)的结点，移动指针指向即可。

             {

                 pre = cur;

                 cur = cur->next;

             }

         }

         // 将两部分连接起来

         // 将原始链表中小于x(< x)的部分和原始链表中大于等于x(>= x)的部分连接起来

         pre->next = pNew->next;

         head = pHead->next;

         // 释放辅助结点内存空间

         delete pHead;

         delete pNew;

         return head;

     }

 };