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;