2020.10.20 原题：点击此处
要求把链表从： L1->L2->L3->…Ln的排序转变为 L1->Ln->L2->Ln-1->…
做这道题的时候真的立刻就想到了 1、快慢指针找链表中间点（因为改变链表序列之后，原来排序的中点必定是后来排序的结尾。） 题目 2、链表反转（因为可以看出改变链表序列后，Ln是倒放的） 题目 后面做了很多次草稿之后发现昨晚上面那两部之后，就不知道怎么办了。 查了题解发现是缺了链表合并这个步骤我没学过，通过这道题，学会了两个相同长度（或长度差为1）的链表如何进行合并。
空间复杂度O（1） 时间复杂度O（n）
Java版本
class Solution { public void reorderList(ListNode head) { if(head == null){ return; } ListNode slow = head; ListNode fast = head; //找中间点 while(fast != null && fast.next != null && fast.next.next !=null){ slow = slow.next; fast = fast.next.next; } //反转 ListNode pre = reverse(slow.next); //结尾置空，防止产生环 slow.next = null; ListNode cur = head; //两个链表进行合并 while(cur != null && pre !=null){ ListNode L_temp = cur.next; ListNode R_temp = pre.next; cur.next = pre; cur = L_temp; pre.next = cur; pre = R_temp; } } public ListNode reverse(ListNode head){ ListNode pre = null; ListNode cur = head; while(cur != null){ ListNode temp = cur.next; cur.next = pre; pre = cur; cur = temp; } return pre; } }C++版本
class Solution { public: void reorderList(ListNode* head) { if(head == nullptr){ return; } ListNode* mid = searchMidNode(head); ListNode* l1 = head; ListNode* l2 = mid->next; mid->next = nullptr; l2 = reverseList(l2); mergeList(l1, l2); } ListNode* reverseList(ListNode* head){ ListNode* pre = nullptr; ListNode* cur = head; while(cur != nullptr){ ListNode* temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; } ListNode* searchMidNode(ListNode* head){ ListNode* slow = head; ListNode* fast = head; while(fast != nullptr && fast->next != nullptr && fast->next->next != nullptr){ slow = slow->next; fast = fast->next->next; } return slow; } void mergeList(ListNode* l1,ListNode* l2){ ListNode* L_temp; ListNode* R_temp; while(l1!=nullptr && l2!=nullptr){ L_temp = l1->next; R_temp = l2->next; l1->next = l2; l1 = L_temp; l2->next = l1; l2 = R_temp; } } };