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(-);
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;
}
};