给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3. 示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reorder-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：(常规解法）
首先要找出分割的节点，即链表的中点位置（注意这里无论链表是奇数个节点还是偶数个节点，对应的重点都是一样的）；将中点位置的后面一部分链表翻转；进行合并。找中点可以使用快慢指针，而链表翻转以前的题做过。合并链表想了半天（菜是原罪）合并的时候主要需要的是要保存节点的下一位置。
代码实现：
/** * 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; ListNode* mid = middleNode(head); ListNode* pre_list = head; ListNode* back_list_tmp = mid->next; mid->next = nullptr; ListNode* back_list = reverse(back_list_tmp); meger(pre_list,back_list); } ListNode* middleNode(ListNode* head) { ListNode* slow = head; ListNode* fast = head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; } return slow; } ListNode* reverse(ListNode* head) { ListNode* pre = NULL; ListNode* cur = head; if(!head) return NULL; while(cur) { ListNode* next = cur->next;//先保存后继节点的值 cur->next = pre; pre = cur; cur = next; } return pre; } void meger(ListNode* l1,ListNode* l2) { ListNode *p1 = nullptr; ListNode *p2 = nullptr; while(l1 && l2) { p1 = l1->next;//保存节点的下一位置 p2 = l2->next; l1->next = l2; l1 = p1; l2->next = p1; l2 = p2; } } };思路二：利用一个数组来保存链表的索引，提供随机访问能力，然后再利用双指针法。代码简单易懂。
/** * 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; vector<ListNode*> temp; ListNode* cur = head; while(cur) { temp.push_back(cur); cur = cur->next; } int left = 0; int right = temp.size() - 1; while(left < right) { temp[left]->next = temp[right]; temp[right--]->next = temp[++left]; } temp[left]->next = nullptr; } };