Day04–链表–24. 两两交换链表中的节点，19. 删除链表的倒数第 N 个结点，面试题 02.07. 链表相交，142. 环形链表 II

记录：三指针法，自己一次性做的。草稿纸画图。一定要画图。

思路：1、先解决(head == null || head.next == null)的情况，这样的话，剩下的情况都至少有两个节点

2、因为是修改链表，最好有个虚拟头结点。

3、pre等于要修改的前一个节点，left和right就是要交换的节点。

4、当pre没有下一个结点的时候可以退出了（当只有left没有right的时候也可以退出了，left不用和谁交换）

5，交换的三部曲。因为有三个指针，随便的顺序感觉都可以，画个图理解一下就可以了。把各个节点的next修改完之后，pre = left，就可以进入下一轮循环了。

class Solution {public ListNode swapPairs(ListNode head) {if (head == null || head.next == null) {return head;}ListNode preHead = new ListNode();preHead.next = head;ListNode pre = preHead;while (pre.next != null) {ListNode left = pre.next;ListNode right = null;if (left.next != null) {right = left.next;} else {break;}ListNode tem = right.next;pre.next = right;right.next = left;left.next = tem;pre = left;}return preHead.next;}
}

推荐阅读：来自《代码随想录》

• while (prev.next != nu11 && prev.next.next != nu11) 这边为什么是&& 不是|| 一个是对于偶数个结点的判断 一个是奇数个结点 那不应该是||的关系吗？
  • 奇数节点就不需要交换了，所以只有满足后面有偶数个节点的时候才会进入循环
• 循环条件，什么情况应该判断指针本身为空呢?
  • 可以看这个这个遍历的指针最后需要走到哪里 需不需要对最后一个节点做操作

记录：自己凭着记忆写出来的。不是背，而是看到这类题会做了。（ps：前几天刚做过）

思路：右指针先走n步，左指针再出发，当右指针到结尾的时候，左指针就是要删除的节点的前节点，刚好可以用left.next = left.next.next;

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 思路：右指针先走n步，左指针再出发，// 当右指针到结尾的时候，左指针就是要删除的节点的前节点，刚好可以用left.next = left.next.next;ListNode preHead = new ListNode();preHead.next = head;ListNode left = preHead;ListNode right = preHead;for (int i = 0; i < n; i++) {right = right.next;}while (right.next != null) {right = right.next;left = left.next;}left.next = left.next.next;return preHead.next;}
}

思路：// 要末端对齐
// 1.指针同时指向末尾
// 2. 长链先走gap步
// 当相等返回指针，当指针指向null则表示不相交，退出。

public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 要末端对齐// 1.指针同时指向末尾// 2. 长链先走gap步// 当相等返回指针，当指针指向null则表示不相交，退出。ListNode pa = headA;ListNode pb = headB;int lenA = 0;int lenB = 0;// 这里不是pa.next != null,犯错了一次。while (pa != null) {pa = pa.next;lenA++;}while (pb != null) {pb = pb.next;lenB++;}if (lenB > lenA) {ListNode temp = headA;headA = headB;headB = temp;int tem = lenA;lenA = lenB;lenB = tem;}int gap = lenA - lenB;pa = headA;pb = headB;while (gap-- > 0) {pa = pa.next;}while (pa != null && pb != null) {if (pa == pb) {return pa;}pa = pa.next;pb = pb.next;}return null;}
}

发现一个很有意思的解法：合并链表实现同步移动

假设链表没有相遇，A链表长度为a，B链表长度为b，p1和p2指针走过的长度都是a+b，之后就一起等于null了，返回p1就是null

假设链表相遇了，A链相遇前长度为a.left，相遇后长度为a.right；b链相遇前长度为b.left，相遇后条件为b.right。——所以p1指针走的路是a.left+a.right+b.left；p2指针走的长度为b.left+b.right+a.left。已知a.right==b.right（相遇后到末尾长度一样），所以p1和p2走相同的路，就可以到相交点

// (版本二) 合并链表实现同步移动
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// p1 指向 A 链表头结点，p2 指向 B 链表头结点ListNode p1 = headA, p2 = headB;while (p1 != p2) {// p1 走一步，如果走到 A 链表末尾，转到 B 链表if (p1 == null) {p1 = headB;} else {p1 = p1.next;}// p2 走一步，如果走到 B 链表末尾，转到 A 链表if (p2 == null) {p2 = headA;} else {p2 = p2.next;}}return p1;}
}

// 写法二：
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode p1 = headA, p2 = headB;while (p1 != p2) {p1 = p1 == null ? headB : p1.next;p2 = p2 == null ? headA : p2.next;}return p1;}
}

推荐阅读：来自《代码随想录》
1、值相等并不是引用地址相等；2、并不是每道题都需要用虚拟头结点

记录：自己根据回忆写的，解题思路是记得的。但是“当fast与slow相遇之后，来一个temp=head，从头开始和slow走相同的步数就是起点了”，这个理论成立不会证明。或者说，就算记住了这题的证明，来一题类似的题目，自己也不会根据公式推理。

思路：// 思路：快指针2步/会合，慢指针1步/会合；
// 当快慢指针相遇的时候，定义一个temp指针从头走，慢指针也走，当slow==temp的时候，就是环的起点
// 查找一般是不用preHead的

public class Solution {public ListNode detectCycle(ListNode head) {// 思路：快指针2步/会合，慢指针1步/会合；// 当快慢指针相遇的时候，定义一个temp指针从头走，慢指针也走，当slow==temp的时候，就是环的起点// 查找一般是不用preHead的if (head == null || head.next == null) {return null;}ListNode fast = head;ListNode slow = head;while (fast != null || slow != null) {if (fast.next == null || fast.next.next == null) {return null;}fast = fast.next.next;slow = slow.next;if (fast == slow) {ListNode temp = head;while (temp != slow) {temp = temp.next;slow = slow.next;}return temp;}}return null;}
}