给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
输入: head = [1,2,3,4]
输出: [1,4,2,3]
示例 2:
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]
提示：
链表的长度范围为 [1, 5 * 104]
1 <= node.val <= 1000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/LGjMqU
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路及方法
用线性表按序存储每一个节点，然后用双指针链接是比较常规的办法，但是会用O(n)的空间。我们采用将链表后半部分反转，然后将前半部分后半部分合并即可在O(1)的空间解决。
这道题是道好题，分别写三个子函数处理：反转链表、找到链表中点、链表合并。这里说下找到链表中点，使用快慢指针的方法，快指针一次走两步，慢指针一次走一步，代码为：
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
但是这道题要找到中点的前一个节点，因为要把链表的前后部分断链，所以代码为：
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
整体方法为：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public void reorderList(ListNode head) {
if (head == null) return;
ListNode mid = findMiddleNode(head);
ListNode head1 = head;
ListNode head2 = mid.next;
// 断链
mid.next = null;
// 后半部分链表反转
head2 = reverse(head2);
// 合并链表
mergeList(head1, head2);
}
// 反转链表
public ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
// 移动指针
prev = curr;
curr = next;
}
return prev;
}
// 寻找链表中间节点前一节点，奇数长度是中间链表，偶数长度是前半部分结尾
public ListNode findMiddleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
// 链表合并
public void mergeList(ListNode head1, ListNode head2) {
ListNode pt1 = head1;
ListNode pt2 = head2;
while (pt1 != null && pt2 != null) {
ListNode next1 = pt1.next;
ListNode next2 = pt2.next;
// 链接
pt1.next = pt2;
pt1 = next1;
pt2.next = pt1;
pt2 = next2;
}
}
}
结果如下：
