題目描述：給鏈表如L: L0→L1→…→Ln-1→Ln，將其重新排序?yàn)長0→Ln→L1→Ln-1→L2→Ln-2→…臭蚁，要求空間復(fù)雜度為O(1)涧窒，且不修改結(jié)點(diǎn)的值。
分析：若沒有要求菩帝，可以先遍歷鏈表在數(shù)組中記錄每個結(jié)點(diǎn)的值，然后修改鏈表即可。純鏈表操作就要在指針上做處理了呼奢，先找到中間結(jié)點(diǎn)斷開宜雀，將后半截鏈表轉(zhuǎn)置后與前半段merge。時間復(fù)雜度O(n)握础，空間O(1)辐董。
代碼：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if (!head || !head -> next) return ;
ListNode *slow = head, *fast = head, *pre = 0;
//設(shè)快慢指針用于找到鏈表中間結(jié)點(diǎn)，slow指針每次走一步禀综，fast走兩步简烘，fast到鏈表尾結(jié)點(diǎn)時slow就在中間結(jié)點(diǎn)
while (fast && fast -> next) //由于fast一次走兩步，故既可能直接跳過尾結(jié)點(diǎn)定枷，也可能最后正好到尾結(jié)點(diǎn)孤澎，即鏈表結(jié)點(diǎn)個數(shù)奇偶的問題
{
pre = slow;
slow = slow -> next;
fast = fast -> next -> next;
}
pre -> next = nullptr; //pre是前半段的最后一個結(jié)點(diǎn)
slow = reverse(slow); //將后半段轉(zhuǎn)置
//merge兩鏈表
ListNode * cur = head;
while (cur -> next)
{
ListNode *tmp = cur -> next;
cur -> next = slow;
slow = slow -> next;
cur -> next -> next = tmp;
cur = tmp;
}
cur -> next = slow;
}
//轉(zhuǎn)置兩鏈表不是用的頭插法，而是直接設(shè)三個指針指向連續(xù)的三個結(jié)點(diǎn)欠窒，在從前向后遍歷的過程中修改當(dāng)前cur所指結(jié)點(diǎn)的指針覆旭，指向其原前結(jié)點(diǎn)。
ListNode* reverse(ListNode *head)
{
if (!head || !head -> next) return head;
ListNode *pre = head;
for (ListNode *cur = head -> next, *nx = cur -> next;
cur;
pre = cur, cur = nx, nx = nx ? nx -> next : nullptr)
cur -> next = pre;
head -> next = nullptr;
return pre;
}
};
