力扣143重排链表
力扣143重排链表
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;