143. 重排链表

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

输入：head = [1,2,3,4]
输出：[1,4,2,3]

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

‍

解：

最初我是这样来写的：

class Solution {public void reorderList(ListNode head) {if (head == null || head.next == null) return;List<ListNode> list = new ArrayList<>();ListNode node = head;while (node != null) {list.add(node);node = node.next;}int i = 0, j = list.size() - 1;while (i < j) {list.get(i).next = list.get(j);i++;list.get(j).next = list.get(i);j--;}list.get(i).next = null; }
}

观看题解后发现，好嘛，还能这么干。

那我们就很明确了，先找到中间节点、再将后半部分反转、接下来交叉合并。

寻找链表的中间节点

这一步呢十分的简单，只需要一个快慢指针就可以解决。

设置一个慢指针一次走一步，设置一个快指针一次走两步。最后快指针走到头，慢指针的位置就是节点的中间位置了。

‍public ListNode findMidNode(ListNode head){ListNode fast = head;ListNode slow = head;while(fast.next != null && fast.next.next != null){slow = slow.next;fast = fast.next.next;}return slow;}

但是这时候有个问题，代码中判断条件上判断了两次fast。fast.next != null && fast.next.next != null

Q:这是为什么呢？

A:引入如果不检查下一个节点是否为空，直接跳两步，就很可能造成空指针异常

快指针每次移动两步（fast = fast.next.next），但移动的前提是：
第一步：fast.next 必须存在（否则无法访问 fast.next.next）。
第二步：fast.next.next 必须存在（否则第二步会指向 null）。
因此，循环条件必须确保这两个节点均非空，才能让快指针安全跳跃。
并且！顺序一定要先判断fast.next再判断fast.next.next

反转链表

public ListNode reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while(cur != null){ListNode temp = cur.next; //防止断层，先存起来cur.next = pre; //指向前一个，反转//进行下一次循环pre = cur; //下一次循环中，pre为当前元素cur = temp; // 下一次循环中，cur为当前元素的下一个。为什么不用cur.next呢？因为我们进行了反转操作，所以找不到下个了，这也是我们之前暂存cur.next的原因。}return pre;}

反转链表也比较好理解，重要的就是要存下来下一个节点

首先我们来想，反转链表不就是1指向null，2指向1，3指向2吗？

所以直接让pre = null，cur =1

反转不就是cur.next = pre (1->null)

那接下来呢？我们想一想，接下来是不是就应该让2指向1了

好那就让pre = 1，cur = 2

反转不也是cur.next = pre（2->1）

没问题吧，那我们来解决pre和cur是怎么变成1和2的。

pre=1，这个并不难，让pre = cur（在第一步cur=1的时候）就可以解决了
那cur=2呢？2是我们正常链表中1的下一个也就是1.next = 2。但是我们在上面已经把1和2切断了。链表变成了1->null 2->3->4->5

那我们是不是可以在一开始可以用一个ListNode先暂存起来2，也就是1.next

ok那我们来梳理一下，核心代码是不是就出来了

‍ListNode temp = cur.next; //防止断层，先存起来
cur.next = pre; //指向前一个，反转
//进行下一次循环的赋值
pre = cur; //下一次循环中，pre为当前元素
cur = temp; // 下一次循环中，cur为当前元素的下一个。为什么不用cur.next呢？因为我们进行了反转操作，所以找不到下个了，这也是我们之前暂存cur.next的原因。

交叉合并

交叉合并的代码就很简单了

public void mergeList(ListNode l1,ListNode l2){ListNode l1t;ListNode l2t;while (l1 != null && l2 != null) {l1t = l1.next;l2t = l2.next;l1.next = l2;l1 = l1t;l2.next = l1;l2 = l2t;}}

第一步我们是不是直接l1.next=l2即可。也就是1->5

那接下来，我们怎么怎么让l1指向2呢？

所以我们在前面需要暂存temp1 = l1.next

让l1 = temp1；接下来l2.next = l1就可以了

那l2又怎么指向4呢？和前面一样temp2 = l2.next，l2 = temp2即可

所以也就有了我们上面的核心代码

l1t = l1.next;
l2t = l2.next;l1.next = l2;
l1 = l1t;l2.next = l1;
l2 = l2t;

‍