刷题计划 day4 【双指针、快慢指针、环形链表】链表下
⚡刷题计划day4继续，可以点个免费的赞哦~
下一期将会开启哈希表刷题专题，往期可看专栏，关注不迷路，
您的支持是我的最大动力🌹~
目录
⚡刷题计划day4继续，可以点个免费的赞哦~
下一期将会开启哈希表刷题专题，往期可看专栏，关注不迷路，
您的支持是我的最大动力🌹~
题目一：19. 删除链表的倒数第 N 个结点
法一：计算链表长度
法二：双指针
题目二：面试题 02.07. 链表相交
法一：双指针
法二：合并链表实现同步移动
题目三：142. 环形链表 II
法一：快慢指针法
1.判断链表是否有环
2.如果有环，如何找到环的入口
2.1 n==1
2.2 n>1
法二：哈希表
题目一：19. 删除链表的倒数第 N 个结点
leetcode:19. 删除链表的倒数第 N 个结点
(https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/)
法一：计算链表长度
常规思路：先遍历得到链表长度L，然后再次遍历到 L-n+1个结点，便是我们需要删除的结点；
这里我们还是使用虚拟头结点统一，于是从虚拟结点开始遍历L-n+1个结点，它的下一个结点便是我们要删除的结点，这样我们只需修改一次指针，就可完成删除操作。
如图辅助理解：
AC代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyHead = new ListNode();dummyHead.next=head;ListNode cur = dummyHead;int length = getLength(head);for (int i=1;i<length-n+1;i++){cur = cur.next;}if(cur.next!=null){//避免空指针cur.next = cur.next.next;//删除操作}return dummyHead.next;
}public int getLength(ListNode head){int length = 0;while(head != null){length++;head=head.next;}return length;}
}法二：双指针
主要思路：
要删除倒数第n个，我们可以使用双指针，这样不用去求长度；
保持一个相差n的区间，fast在前,slow在后。这样等fast走到链表末尾，slow对应的就是我们要删除的结点；
因为链表删除我们需要通过前一个结点，所以将相差区间设为n+1，可以结合图理解：
AC代码
class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummyHead = new ListNode();dummyHead.next=head;ListNode fast = dummyHead;ListNode slow = dummyHead;
// 只要快慢指针相差 n 个结点即可for (int i=1;i<=n+1;i++){fast = fast.next;}while (fast!=null){fast = fast.next;slow = slow.next;}
if(slow.next!=null){slow.next = slow.next.next;}return dummyHead.next;}
}题目二：面试题 02.07. 链表相交
leetcode：面试题 02.07. 链表相交
(https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/)
简单来说，就是求两个链表交点节点的指针。 这里要注意，交点不是数值相等，而是指针相等。
为了方便举例，假设节点元素数值相等，则节点指针相等。
看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：
我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置，如图
此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。
否则循环退出返回空指针。
AC代码
法一：双指针
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 初始化两个链表的当前节点ListNode cur1 = headA;ListNode cur2 = headB;// 初始化两个链表的长度int len1 = 0;int len2 = 0;
// 求cur1长度while (cur1 != null) {len1++;cur1 = cur1.next;}// 求cur2长度while (cur2 != null) {len2++;cur2 = cur2.next;}
// 重新初始化两个链表的当前节点cur1 = headA;cur2 = headB;
// 如果第一个链表比第二个短，交换两个链表的头节点和长度if (len1 < len2) {//1. swap (len1, len2);int temp = len1;len1 = len2;len2 = temp;//2. swap (cur1, cur2);ListNode temNode = cur1;cur1 = cur2;cur2 = temNode;}
// 计算长度的差值int gap = len1 - len2;// 移动较长链表的当前节点，使cur1与cur2的末尾位置对齐，看图while (gap-- > 0) {cur1 = cur1.next;}
// 同时遍历两个链表，遇到相同则直接返回while (cur1 != null) {if (cur1 == cur2) {return cur1; // 返回相交的节点}cur1 = cur1.next;cur2 = cur2.next;}
// 如果两个链表没有相交，返回nullreturn null;}
}法二：合并链表实现同步移动
主要思路：
-
同步移动指针：
-
使用一个
while循环，只要p1和p2没有相遇，就继续移动指针。 -
对于
p1，如果它到达了链表A的末尾（即p1为null），则将它移动到链表B的头部，重新开始遍历。 -
对于
p2，如果它到达了链表B的末尾（即p2为null），则将它移动到链表A的头部，重新开始遍历。
-
-
相遇即相交：
-
当两个指针
p1和p2相遇时，它们指向的就是链表相交的节点。因为两个指针最终都会遍历完两个链表，如果链表有相交点，它们最终会在相交点相遇。
-
-
返回结果：
-
一旦
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;}
}题目三：142. 环形链表 II
leetcode：142. 环形链表 II
(https://leetcode.cn/problems/linked-list-cycle-ii/description/)
法一：快慢指针法
判断链表是否有环，我们一般可以使用快慢指针法
此题还是有一定难度，考察了对链表环的判断，已经需要进行数学运算，下文会进行详细解释。
对于此题大致分为两大步：
1.判断链表是否有环
2.如果有环，如何找到环的入口
1.判断链表是否有环
分别定义fast,slow指针，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
2.如果有环，如何找到环的入口
这步已经可以判断链表是否有环了，接下来是寻找环的入口，需要用到一点数学运算。
假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：
那么当相遇时：
slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。
加深理解注：
1.fast指针为什么 n (y + z)？ 因为fast比slow快，fast进入圈后至少需要一圈后追反超slow，由此也可知道，n>=1（后续解题会用）。
2.为什么slow就不用比如k(y+z)？ 因为slow进入圈后在一圈内一定会被fast追上
3.那为什么slow一圈内就一定会被fast追上呢？ 可以这样通俗理解：首先fast会比slow快1，如果slow走一圈，fast就会走两圈，那一定会追上。
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 slow指针走过的节点数 * 2 = fast指针走过的节点数，所以可以列出方程：
(x + y) * 2 = x + y + n (y + z)
因为我们要找环形入口，即需要找x，将x单独放出来化简：
x = n (y + z) - y
但是我们看一下这个式子呢，也发现不了什么，我们是想通过右边的参数来求x，但发现目前右侧也没啥特殊形式，还有个-y。于是我们可以提一个(y+z)出来，
x = (n - 1) (y + z) + z(此处n>=1，前面有解释)
此时就明了了。
2.1 n==1
当 n为1的时候，公式就化解为 x = z，
这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。
让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。
2.2 n>1
那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。
其实这种情况和n为1的时候效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。
代码如下：
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;}
}法二：哈希表
这个思路就简单很多，时间复杂度：O(N)，空间复杂度：O(N)；
但第一种双指针的解法也需要掌握，时间复杂度：O(N)，空间复杂度：O(1)。
关于哈希表我们下期也会做相应的专题刷题。
主要思路：遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。
代码：
详细见注解
public class Solution {public ListNode detectCycle(ListNode head) {// 初始化指针pos指向头结点ListNode pos = head;// 使用HashSet来存储已经访问过的节点Set<ListNode> visited = new HashSet<ListNode>();
// 遍历链表while (pos != null) {// 如果当前节点已经被访问过，说明存在环，返回当前节点if (visited.contains(pos)) {return pos;} else {// 否则，将当前节点添加到visited集合中visited.add(pos);}// 移动到下一个节点pos = pos.next;}
// 如果遍历完整个链表都没有发现环，返回nullreturn null;}
}