題?鏈接：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;}}}
}