Reorder List

    You must do this in-place without altering the nodes’ values.

    For example,
    Given , reorder it to {1,4,2,3}.

    " class="reference-link">题解1 - 链表长度(TLE)

    既然依赖链表长度信息，那么要做的第一件事就是遍历当前链表获得其长度喽。获得长度后即对链表进行遍历，小心处理链表节点的断开及链接。用这种方法会提示 TLE，也就是说还存在较大的优化空间！

    C++ - TLE

    1. 异常处理，对于节点数目在两个以内的无需处理。
    2. 遍历链表，第一个索引处的节点使用last表示，第二个索引处的节点的前一个节点使用表示。
    3. 处理链表的链接与断开，迭代处理下一个last。

    复杂度分析

    1. 遍历整个链表获得其长度，时间复杂度为 $$O(n)$$.
    2. 双重for循环的时间复杂度为 $$(n-2) + (n-4) + … + 2 = O(\frac{1}{2} \cdot n^2)$$.
    3. 总的时间复杂度可近似认为是 $$O(n^2)$$, 空间复杂度为常数。

    C++

    源码分析

    相对于题解1，题解2更多地利用了链表的常用操作如反转、找中点、合并。

    1. 找中点：我在九章算法模板的基础上增加了对head->next的异常检测，增强了鲁棒性。
    2. 反转：非常精炼的模板，记牢！

    复杂度分析

    找中点一次，时间复杂度近似为 O(n). 反转链表一次，时间复杂度近似为 O(n/2). 合并左右链表一次，时间复杂度近似为 O(n/2). 故总的时间复杂度为 O(n).