算法 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;}
}

法二：合并链表实现同步移动

主要思路：

1. 同步移动指针：

   • 使用一个 while 循环，只要 p1 和 p2 没有相遇，就继续移动指针。

   • 对于 p1，如果它到达了链表 A 的末尾（即 p1 为 null），则将它移动到链表 B 的头部，重新开始遍历。

   • 对于 p2，如果它到达了链表 B 的末尾（即 p2 为 null），则将它移动到链表 A 的头部，重新开始遍历。

2. 相遇即相交：

   • 当两个指针 p1 和 p2 相遇时，它们指向的就是链表相交的节点。因为两个指针最终都会遍历完两个链表，如果链表有相交点，它们最终会在相交点相遇。

3. 返回结果：

   • 一旦 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;}
}