題目描述：給鏈表如L: L0→L1→…→Ln-1→Ln，將其重新排序為L0→Ln→L1→Ln-1→L2→Ln-2→…，要求空間復(fù)雜度為O(1)，且不修改結(jié)點的值。

分析：若沒有要求，可以先遍歷鏈表在數(shù)組中記錄每個結(jié)點的值，然后修改鏈表即可。純鏈表操作就要在指針上做處理了，先找到中間結(jié)點斷開，將后半截鏈表轉(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é)點，slow指針每次走一步，fast走兩步，fast到鏈表尾結(jié)點時slow就在中間結(jié)點
        while (fast && fast -> next)      //由于fast一次走兩步，故既可能直接跳過尾結(jié)點，也可能最后正好到尾結(jié)點，即鏈表結(jié)點個數(shù)奇偶的問題
        {
            pre = slow;
            slow = slow -> next;
            fast = fast -> next -> next;
        }
        pre -> next = nullptr;              //pre是前半段的最后一個結(jié)點
        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é)點，在從前向后遍歷的過程中修改當(dāng)前cur所指結(jié)點的指針，指向其原前結(jié)點。
    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;
    }
};