链接：lc143. 重排链表
可以采用线性表 vector<ListNode*> 记录所有的节点，然后下标直接访问进行两两之间的逆置，也是官方题解方法一。空间复杂度较高，不谈了。
采用题解中的方法二：寻找链表中点 + 链表逆序 + 合并链表
通过观察能够发现，链表的后半段各个节点会插入到链表前半段两个节点的中间，但是链表没办法逆序访问，所以我们可以找到链表中点，并将后半段链表进行逆置，然后采用双指针一个指向头节点，一个指向中点进行合并。
思路有了，紧接着考虑边界情况，链表节点个数奇偶的情况，记链表节点数为 n，中间节点为 mid：
mid 节点求解，如果是奇数个节点时，可以将中间的节点归结到前半段，则为 ⌊ n + 1 2 ⌋ \lfloor \frac {n + 1}{2} \rfloor ⌊2n+1⌋ 等价于 ⌈ n 2 ⌉ \lceil \frac{n}{2} \rceil ⌈2n⌉奇数情况：很好说明，mid->next = NULL; 即可偶数情况：由于参考示例 1，能够发现是 mid->next->next = NULL。偶数节点的边界情况，若为 1->2->NULL，则 mid 会指向 1，同时进行链表反转后，1, 2 的 next 会互相指向对方(可以自行在 lc 中 cout 观察)，然后 mid->next->next = NULL 就可以顺利使得 2 的 next 指针指向空。至此分析完毕了，边界情况了考虑完毕了，我们再来考虑一种情况：
在合并前、中、后处理尾指针为空的情况？例如 1->2->3->4->NULL 我们求取了 mid = 2，然后进行后半段链表反转，反转完毕后为 1->2<->3<-4 注意 2<->3 在此已经形成了环。然后，设置 p = 1, a = 4 来开始合并，合并的次数就是 n / 2 次第一次合并，将 4 插入 1、2 之间，变成 1->4->2<->3，此时 p = 2, a = 3，i = 1如果在合并后处理尾指针为空的情况，偶数节点链表的 mid->next 节点会形成一个自环。然后 mid->next->next = NULL 刚好可以处理如果在合并前处理尾指针为空的情况，则在最后更新的时候，依旧会形成 3 的自环，但是最后又没有处理，就死循环了。可以在 lc 上将代码放到中间看看，可以得到死循环的代码，然后 copy 到尾部再处理一遍就能够通过了当为奇数节点时，在中间处理尾指针是可行的，可自己画图分析~所以将尾指针的空处理直接放到最后即可，可以统一起来处理尾指针代码：
if (n % 2) mid->next = NULL; else mid->next->next = NULL;很综合的一道练习题，上述的坑基本都才过一遍了，链表的题目十分建议画图理解，各个指针之间的关系容易把自己绕进去。
参见代码如下：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: void reorderList(ListNode* head) { if (!head) return ; int n = 0; for (auto e = head; e; e = e->next) ++n; auto mid = head; // 在此将奇数节点归结到前半段区间 for (int i = 0; i < (n + 1) / 2 - 1; ++i) mid = mid->next; auto a = mid, b = a->next; // 后半段链表反转，1->2->3->4->NULL变成1->2<->3<-4 for (int i = 0; i < n / 2; ++i) { auto c = b->next; b->next = a; a = b; b = c; } // 最后处理尾指针统一奇偶情况 // 偶数节点时，mid节点的下一个节点会形成自环，则mid->next->next就可以让其为null // 奇数节点时，仅在中间处理是可以的 // 为了统一，统一在尾部进行处理，也可以双处理，验证下奇数节点的处理位置 // if (n % 2) mid->next = NULL; // else mid->next->next = NULL; auto p = head, q = a; for (int i = 0; i < n / 2; ++i) { auto o = q->next; q->next = p->next; p->next = q; p = q->next, q = o; } if (n % 2) mid->next = NULL; else mid->next->next = NULL; } };