题⽬链接：143. 重排链表

题⽬描述：

给定⼀个单链表 L 的头节点 head ，单链表 L 表⽰为：
L(0) → L(1) → … → L(n - 1) → L(n)
请将其重新排列后变为：
L(0) → L(n) → L(1) → L(n - 1) → L(2) → L(n - 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 * 10(4)]
• 1 <= node.val <= 1000

解法：

算法思路：

画图画图画图，重要的事情说三遍~
1.找中间节点；
2.中间部分往后的逆序；
3.合并两个链表

算法代码：

/**
 * 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 || head.next == null || head.next.next == null) return;
	 // 1. 找链表的中间节点 - 快慢双指针（⼀定要画图分析 slow 的落点）
	 ListNode slow = head, fast = head;
	 while(fast != null && fast.next != null){
		 slow = slow.next;
		 fast = fast.next.next;
	 }
	 // 2. 把 slow 后⾯的部分给逆序 - 头插法
	 ListNode head2 = new ListNode(0);
	 ListNode cur = slow.next;
	 slow.next = null; // 把两个链表分离
	 while(cur != null){
		 ListNode next = cur.next;
		 cur.next = head2.next;
		 head2.next = cur;
		 cur = next;
	 }
	 // 3. 合并两个链表 - 双指针
	 ListNode cur1 = head, cur2 = head2.next;
	 ListNode ret = new ListNode(0);
	 ListNode prev = ret;
	 while(cur1 != null){
		 // 先放第⼀个链表
		 prev.next = cur1;
		 prev = cur1;
		 cur1 = cur1.next;
		 // 在合并第⼆个链表
		 if(cur2 != null){
			 prev.next = cur2;
			 prev = cur2;
			 cur2 = cur2.next;
		 }
	 }
 }
}