day04 打卡24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 142.环形链表II
24. 两两交换链表中的节点
1.第一次想的思路：使用count记录当前是第几个节点，每当count为偶数时，进行交换两个相邻的节点。while中代码可以实现，但是当返回头节点的时候不知道怎么放回。因为虚拟节点后的头节点换了。以下是我的思路伪代码：
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
ListNode cur = head;
ListNode temp = null;
int count = 1;
while (cur != null && cur.next != null) {
if (count%2 == 0) {
temp = cur.next;
cur.next = pre;
pre.next = temp;
} else {
pre = cur;
cur = cur.next;
}
count++;
}
// 交换完成，但是找不到头节点
return ？
2.去看了代码随想录。发现了（我思考的）参与交换的节点是2个（即需要交换的两个节点），这就有了上面的短路。而代码随想录的动态图是3个节点的交换，而且不需要count计数，直接把cur变成下一个需要交换的第一个节点即可。如果不满足两个节点，也不需要进入while循环了，无需交换。我写下了以下的代码:
以dummy->1->2->3->4->null为例：
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy; // dummy, next:1
ListNode cur = head; // 1, next: 2
ListNode temp = null;
while (cur != null && cur.next != null) {
pre.next = cur.next; // 这句话让dummy.next = 2
temp = cur.next.next; // 记住 不需要进行交换的后面的节点即3->4->null
cur.next = temp; // 这句话让1.next = 3
// 此时的排序 dummy->2 ; 1->3->4->null
pre.next.next = cur; // 这句话让2.next = 1
// 此时的排序 dummy->2->1->3->4->null
// 下一个进行交换的节点cur是3，pre要是1
pre = cur;
cur = temp;
}
return dummy.next;
}
}
3.递归法。根据03.03的206题目递归法的推出，我写出了对应版本的递归法。递归结束条件==循环结束条件，主体交换操作代码一致。本来我写了return pre.next，但是这样返回的是null，虽然节点排序完成。不需要return数值，这就涉及到了java方法传参数。基本类型总是按值传递。对于对象来说，是将对象的引用也就是副本传递给了方法，在方法中只有对对象进行修改才能影响该对象的值，操作对象的引用时是无法影响对象。
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummy = new ListNode(-1, head);
swapPairs(dummy, head);
return dummy.next;
}
public void swapPairs(ListNode pre, ListNode cur) {
if (cur == null || cur.next == null) {
return;
}
pre.next = cur.next;
ListNode temp = cur.next.next;
cur.next = temp;
pre.next.next = cur;
swapPairs(cur, temp);
}
}
19. 删除链表的倒数第 N 个结点
1.想不出来比较简单的方式。决定先把整个翻转，在去删除，再去翻转。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
head = reserve(head);
head = del(head, n);
return reserve(head);
}
public ListNode del(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
for(int i = 1; i<n ; i++) {
pre = pre.next;
}
pre.next = pre.next.next;
return dummy.next;
}
public ListNode reserve(ListNode head) {
ListNode pre = null;
ListNode cur = head;
ListNode temp = null;
while (cur != null) {
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
2.看来视频讲解在写的代码。主要的思想就是使用快慢指针。首先要删除一个节点需要得到这个节点的前驱节点。
因为链表长度是不变的，我们称呼为size。快指针先走n步，剩下的步数就是size-n。而size-n就是我们正常从链头开始走到需要被删除节点的距离。这时的慢指针还在原点，慢指针和快指针同时开始走路，当快指针到达null（链尾）的时候，慢指针就走到了要删除的节点。
因为我们真的需要操作的是要删除的节点的前一个，所以快指针先走n+1步，慢指针就走size-n-1步，正好到达前驱节点。
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(-1, head);
ListNode fast = dummy;
ListNode slow = dummy;
for (int i = 0; i<n+1 ; i++) {
fast = fast.next;
}
while (fast != null) {
fast = fast.next;
slow = slow.next;
}
// slow现在的位置就是要删除的节点的前驱节点
slow.next = slow.next.next;
return dummy.next;
}
}
面试题 02.07. 链表相交
1.没有思路，直接看代码随想录的.
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode aCur = headA;
ListNode bCur = headB;
int aSize = getSize(headA);
int bSize = getSize(headB);
// 长度查
int gap = Math.abs(aSize - bSize);
if (aSize > bSize) {
// b对齐a的尾巴,操作a指针
for (int i = 0 ; i<gap ; i++) {
aCur = aCur.next;
}
} else {
// a对齐b的尾巴,操作b指针
for (int i = 0 ; i<gap ; i++) {
bCur = bCur.next;
}
}
while (aCur != null && bCur != null) {
if (aCur == bCur) {
return aCur;
}
aCur = aCur.next;
bCur = bCur.next;
}
return null;
}
public int getSize(ListNode head) {
int size = 0;
while (head != null) {
head = head.next;
size++;
}
return size;
}
}
142. 环形链表 II
1.直接看视频，比较清楚 视频链接
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) {
// 说明快慢指针相遇，则一定有环
ListNode index1 = fast; // 相遇的位置
ListNode index2 = head;
while (index1 != index2) {
index1 = index1.next;
index2 = index2.next;
}
return index1;
}
}
return null;
}
}