leetcode 143. Reorder List 、86. Partition List

143. Reorder List

https://www.cnblogs.com/grandyang/p/4254860.html

先将list的前半段和后半段分开，然后后半段进行逆序，然后再连接

class Solution {
public:
    void reorderList(ListNode* head) {
        if(head == NULL)
            return;
        ListNode* p1 = head;
        ListNode* p2 = head;
        while(p2->next != NULL && p2->next->next != NULL){
            p1 = p1->next;
            p2 = p2->next->next;
        }
        p2 = p1->next;
        p1->next = NULL;
        ListNode* pre = NULL;
        while(p2 != NULL){
            ListNode* tmp = p2->next;
            p2->next = pre;
            pre = p2;
            p2 = tmp;
        }
        p1 = head;
        p2 = pre;
        while(p2 != NULL){
            ListNode* tmp1 = p1->next;
            ListNode* tmp2 = p2->next;
            p1->next = p2;
            p2->next = tmp1;
            p1 = tmp1;
            p2 = tmp2;
        }
        return;
    }
};

86. Partition List

这个题和143有点相似，都是用两个指针，分别表示前面满足条件的最后一个，后面满足条件的最后一个。

但143的p2是只管当前指针，但86题p2是当前指针的前一个指针，因为86题需要判断是否满足小于x的条件，但143则不需要。

主循环那部分，只适合下一个指针大于x的情况，所以先通过一个循环找到第一个大于的x的前一个指针。

注意：要申请一个dummy指针保存最终的链表的返回，head指针也可能被排序排乱。

比如下面这种情况：

Input:
[2,1]
2
Output:
[2]
Expected:
[1,2]

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if(head == NULL)
            return NULL;
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode* pre = dummy;
        while(pre->next && pre->next->val < x)
            pre = pre->next;
        ListNode* cur = pre;
        while(cur->next){
            if(cur->next->val >= x)
                cur = cur->next;
            else{
                ListNode* tmp = cur->next;
                cur->next = tmp->next;
                tmp->next  = pre->next;
                pre->next = tmp;
                pre = pre->next;
            }
        }
        return dummy->next;
    }
};