鏈表劃分

描述
給定一個單鏈表和數值x，劃分鏈表使得所有小於x的節點排在大於等於x的節點之前。你應該保留兩部分內鏈表節點原有的相對順序。

樣例 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);
    }
};