Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list's nodes, only nodes itself may be changed.
Example 1:
Given 1->2->3->4, reorder it to 1->4->2->3.Example 2:
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.题意：给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→……注意，不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
C++的写法如下，复制链表指针，然后改变指针走向。注意，最后新链表的尾结点的指针仍然指向原来的下一个结点，需要改为指向空：
class Solution { public: void reorderList(ListNode* head) { if (head == nullptr) return; list<ListNode*> deque; while (head) { deque.push_back(head); head = head->next; } while (!deque.empty()) { if (head == nullptr) { //此时head指向空 head = deque.front(); deque.pop_front(); } else { head->next = deque.front(); head = head->next; deque.pop_front(); } if (!deque.empty()) { head->next = deque.back(); deque.pop_back(); head = head->next; } } if (head != nullptr) head->next = nullptr; } };效率很低，不忍直视：
执行用时：100 ms, 在所有 C++ 提交中击败了8.88% 的用户 内存消耗：20.9 MB, 在所有 C++ 提交中击败了5.04% 的用户如果不使用 list 而使用 vector 的话，有下面的代码，写得更加简洁：
class Solution { public: void reorderList(ListNode* head) { if (head == nullptr) return; vector<ListNode*> v; while (head) { v.push_back(head); head = head->next; } int left = 0, right = v.size() - 1; while (left < right) { v[left]->next = v[right]; v[right--]->next = v[++left]; } v[left]->next = nullptr; } };效率稍微高一点：
执行用时：84 ms, 在所有 C++ 提交中击败了13.14% 的用户 内存消耗：18.8 MB, 在所有 C++ 提交中击败了5.04% 的用户用Java写这一代码：
class Solution { public void reorderList(ListNode head) { LinkedList<ListNode> deque = new LinkedList<>(); ListNode cur = head; while (cur != null) { deque.addLast(cur); cur = cur.next; } while (!deque.isEmpty()) { if (cur == null) { //插入前半部分结点 cur = deque.pollFirst(); } else { cur.next = deque.pollFirst(); cur = cur.next; } cur.next = deque.pollLast(); //插入链表尾部结点 cur = cur.next; } if (cur != null) cur.next = null; } }效率如下，差别太大了：
执行用时：3 ms, 在所有 Java 提交中击败了36.50% 的用户 内存消耗：41.8 MB, 在所有 Java 提交中击败了41.45% 的用户题目原意是希望交换，因此不用双端队列重新拷贝的方法，也可以完成这一道题。做法是：在原链表上操作，首先快慢指针找到中点，然后拆成两个链表，将后面的链表反转，接着遍历两个链表并把后面的结点插入前面的缝隙中。
class Solution { private: ListNode* reverseRecur(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode *newHead = reverseRecur(head->next); head->next->next = head; head->next = nullptr; return newHead; } ListNode* reverseIter(ListNode* head) { if (head == nullptr || head->next == nullptr) return head; ListNode *pre = nullptr, *post = head; while (post) { ListNode *temp = post->next; post->next = pre; pre = post; post = temp; } return pre; } public: void reorderList(ListNode* head) { if (head == nullptr || head->next == nullptr) return; ListNode dummy(0); dummy.next = head; ListNode *lo = &dummy, *hi = &dummy; while (hi && hi->next) { //快慢指针找到链表的中点 hi = hi->next->next; lo = lo->next; } //此时快慢指针将链表分为两段 ListNode *postHead = lo->next; lo->next = nullptr; postHead = reverseRecur(postHead); ListNode *cur = head, *rear = postHead; while (cur && rear) { //插入前端链表的缝隙 ListNode *rearNext = rear->next, *curNext = cur->next; rear->next = curNext; cur->next = rear; rear = rearNext, cur = curNext; } } };虽然时间复杂度仍然是 O ( n ) O(n) O(n) ，但是空间复杂度为 O ( 1 ) O(1) O(1) ：
执行用时：56 ms, 在所有 C++ 提交中击败了43.59% 的用户 内存消耗：18.4 MB, 在所有 C++ 提交中击败了7.86% 的用户