力扣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]
‍
解：
最初我是这样来写的：

1. class Solution {
2.     public void reorderList(ListNode head) {
3.         if (head == null || head.next == null) return;
5.         List<ListNode> list = new ArrayList<>();
6.         ListNode node = head;
7.         while (node != null) {
8.             list.add(node);
9.             node = node.next;
10.         }
12.         int i = 0, j = list.size() - 1;
13.         while (i < j) {
14.             list.get(i).next = list.get(j);
15.             i++;
17.             list.get(j).next = list.get(i);
18.             j--;
19.         }
20.         list.get(i).next = null;
21.     }
22. }

复制代码

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

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

这一步呢十分的简单，只需要一个快慢指针就可以解决。
设置一个慢指针一次走一步，设置一个快指针一次走两步。最后快指针走到头，慢指针的位置就是节点的中间位置了。

1. ‍public ListNode findMidNode(ListNode head){
2.         ListNode fast = head;
3.         ListNode slow = head;
4.         while(fast.next != null && fast.next.next != null){
5.             slow = slow.next;
6.             fast = fast.next.next;
7.         }
8.         return slow;
9.     }

复制代码

但是这时间有个问题，代码中判断条件上判断了两次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
反转链表

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

复制代码

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

首先我们来想，反转链表不就是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那我们来梳理一下，核心代码是不是就出来了

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

复制代码

交叉归并

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

1. public void mergeList(ListNode l1,ListNode l2){
2.         ListNode l1t;
3.         ListNode l2t;
5.         while (l1 != null && l2 != null) {
6.             l1t = l1.next;
7.             l2t = l2.next;
9.             l1.next = l2;
10.             l1 = l1t;
12.             l2.next = l1;
13.             l2 = l2t;
14.         }
15.     }

复制代码

第一步我们是不是直接l1.next=l2即可。也就是1->5
那接下来，我们怎么怎么让l1指向2呢？
所以我们在前面需要暂存temp1 = l1.next
让l1 = temp1；接下来l2.next = l1就可以了
那l2又怎么指向4呢？和前面一样temp2 = l2.next，l2 = temp2即可
所以也就有了我们上面的核心代码

1. l1t = l1.next;
2. l2t = l2.next;
4. l1.next = l2;
5. l1 = l1t;
7. l2.next = l1;
8. l2 = l2t;

复制代码

‍

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。