①：用 vector 存下整个链表，然后按题目要求链起来即可。时间空间 O(n)
②：将链表从中间位置分割为两个链表，并将后半部分链表进行反转，然后再链起来即可。时间 O(n)，空间 O(1)
class Solution { public: void reorderList(ListNode* head) { ListNode *tail = reverseHalfList(head); ListNode *ptr = head; while(tail) { // tail 为 nullptr, 整个链接就完成了. ListNode *ptrNext = ptr -> next; ListNode *tailLast = tail -> next; ptr -> next = tail; tail -> next = ptrNext; ptr = ptrNext; tail = tailLast; } } private: ListNode* reverseHalfList(ListNode *head) { ListNode *slow = head, *quick = head; // 寻找链表中间节点 // 链表结点为单数, slow 停止中间节点. 为偶数 slow 停止在中间第一个结点 while(quick && quick -> next && quick -> next -> next) { slow = slow -> next; quick = quick -> next -> next; } ListNode *slowNext = slow -> next; slow -> next = nullptr; return reverseList(slowNext); } ListNode* reverseList(ListNode *head) { ListNode *pre = nullptr; while(head) { ListNode *nxt = head -> next; head -> next = pre; pre = head; head = nxt; } return pre; } };