Partition List

Partition List(将链表按照某个值分区)

题目描述：

给定一个链表的头结点和一个给定值k。将链表按照左侧的节点都小于k，中间的值等于k，右侧的值大于k的排列方式重新连接链表。对于链表各个分区的内部节点并没有要求有序，但是要求和原链表中的节点顺序一致。

例子：

9->0->4->5->1->NULL。给定的分区值为3的情况下，我们需要返回的链表为：0->1->9->5->4->NULL

解题思路：

主要的思路是我们定义3个分区链表，分别保存小于分区值、等于分区值和大于分区值3种。然后遍历链表不断的将链表的节点加入对应的分区链表中，最后再将三个分区链表连接即可。注意的地方有在连接三个分区的时候，需要考虑各个分区中可能是空的情况。

代码如下：

class listPartition1{
public:
    ListNode* listPartition(ListNode* head, int pivot){
        ListNode* sh = NULL;
        ListNode* se = NULL; // 小于分区值的头节点和尾节点
        ListNode* eh = NULL;
        ListNode* ee = NULL; // 等于分区值的头节点和尾节点
        ListNode* bh = NULL;
        ListNode* be = NULL; // 大于分区值的头节点和尾节点
        ListNode* next = NULL;
        while(head != NULL){
            next = head->next;
            head->next = NULL; // next保存下一个节点后断开当前节点和后续链表的连接
            if (head->val < pivot){
                if (sh == NULL){
                    sh = head;
                    se = head;
                }
                else{
                    se->next = head;
                    se = se->next;
                }             // 将符合条件的节点放入对应分区
            } else if (head->val == pivot){
                if (eh == NULL){
                    eh = head;
                    ee = head;
                }
                else{
                    ee->next = head;
                    ee = ee->next;
                }          // 将符合条件的节点放入对应分区
            }else{
                if (bh == NULL){
                    bh = head;
                    be = head;
                }
                else{
                    be->next = head;
                    be = be->next;
                }        // 将符合条件的节点放入对应分区
            }
            head = next; // 然后head继续遍历
        }
        if (sh != NULL){
            if (eh != NULL) {
                se->next = eh;
                ee->next = bh;
            }
            else
                se->next = bh;
            return sh;
        }
        else{
            if (ee != NULL) {
                ee->next = bh;
                return ee;
            }
            else
                return bh;  //需要注意不同的分区可能为空的情况
        }
    }
};