链表划分

样例 1：  输入：  list = null x = 0 输出：  null 解释：  空链表本身满足要求

样例 2：  输入：  list = 1->4->3->2->5->2->null x = 3 输出：  1->2->2->4->3->5->null 解释：  要保持原有的相对顺序。

/**  * Definition of singly-linked-list:  * class ListNode {  * public:  *     int val;  *     ListNode *next;  *     ListNode(int val) {  *        this->val = val;  *        this->next = NULL;  *     }  * }  */  class Solution { public:     /**      * @param head: The first node of linked list      * @param x: An integer      * @return: A ListNode      */     ListNode* partition(ListNode *head, int x) {         // write your code here                  if(head == NULL)         {             return head;         }         // sH和sT指向同一段链表，sH一直指向这段链表的头，然后依靠sT来为这段链表添加新节点；         ListNode *sH = NULL; //small head;         ListNode *sT = NULL; //small tail;         // ListNode *eH = NULL; //equal head;         // ListNode *eT = NULL; //equal tail;         // ListNode *mH = NULL; //big head;         // ListNode *mT = NULL; //big tail;         //同理， meH和meT指向同一段链表，meH一直指向这段链表的头，然后依靠meT来为这段链表添加新节点；         ListNode *meH = NULL;         ListNode *meT = NULL;          ListNode *next = NULL; //save next ListNode         // every ListNode distributed to three lists         //以输入list=1->4->3->2->5->2->null;x=3为例         while(head != NULL)         {             next = head->next;             // 可以看到每次插入的head都是一个节点，其next为NULL；             head->next = NULL;             if(head->val < x)             {                 if(sH == NULL)                 {                     //sH和sT指向同一个当前head，其val为1                     sH = head;                     sT = head;                 }                 else                 {                     //sT的下一个为2,即1->2，记住此时只是改变了sT,但是sH一直都指向这段链表的首端，其值为1;                     sT->next = head;                     // 改变sT，使其指向新插入的链表，新链表其值为2;                     sT = head;                 }             }             // else if(head->val == x)             else             {                 if(meH == NULL)                 {                     //meH和meT指向同一个当前head，其val为4                     meH = head;                     meT = head;                 }                 else                 {                     //meT的下一个为3,即4->3，记住此时只是改变了meT,但是meH一直都指向这段链表的首端，其值为4;                     meT->next = head;                     // 改变sT，使其指向新插入的链表，新链表其值为3;                     meT = head;                 }             }             // else             // {             //     if(mH == NULL)             //     {             //         mH = head;             //         mT = head;             //     }             //     else             //     {             //         mT->next = head;             //         mT = head;             //     }             // }             head = next;         }          //small and equal reconnect         if(sT != NULL)//如果有小于x的区域         {             sT->next = meH;             // eT = eT==NULL?sT:eT; //下一步，谁去连大于x区域的头，谁就变成eT;         }         //上面的if，不管运行了没有，eT         //all reconnect         // if(eT != NULL)  //如果小于x的区域和等于x的区域，不是都没有         // {         //     eT->next =  mH;         // }         // return sH != NULL ? sH : (eH != NULL ? eH : mH);         return (sH != NULL ? sH : meH);     } };