【牛客面试必刷TOP101】Day16.BM7 链表中环的入口结点和BM9 删除链表的倒数第n个节点

作者简介：大家好，我是未央；

博客首页：未央.303

系列专栏：牛客面试必刷TOP101

每日一句：人的一生，可以有所作为的时机只有一次，那就是现在！！！！！

文章目录

前言

一、链表中环的入口结点

题目描述

题目解析

二、删除链表的倒数第n个节点

题目描述

题目解析

总结

---

---

前言

一、链表中环的入口结点

题目描述

描述：

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

---

举例说明：

输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

---

输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

返回值描述：

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

---

数据范围： n≤10000，1<=结点值<=10000；

要求：空间复杂度 O(1)，时间复杂度 O(n)。

---

示例1：

---

示例2：

---

示例3：

---

题目解析

解题思路：

方法：双指针（推荐使用）

---

思路：

根据题干，不说别的，我们能发现这道题需要完成两个任务：

1. 判断链表是否有环。
2. 在有环的链表中找到环的入口。

---

对于第一个任务，可以参考判断链表中是否有环，主要思想是利用环没有末尾NULL，后半部分一定是环，然后快慢双指针相遇就代表有环。

（具体分析可以参考BM6.判断链表中是否有环）

---

第二个任务：找到环的入口

那我们现在假定已经是一个有环的链表了，那么这个链表中怎么找到环的入口呢？

在慢指针进入链表环之前，快指针已经进入了环，且在里面循环，这才能在慢指针进入环之后，快指针追到了慢指针，不妨假设快指针在环中走了n圈，慢指针在环中走了m圈，它们才相遇，而进入环之前的距离为x，环入口到相遇点的距离为y，相遇点到环入口的距离为z。快指针一共走了x+n(y+z)+y步，慢指针一共走了 x+m(y+z)+y，这个时候快指针走的倍数是慢指针的两倍，则x+n(y+z)+y=2(x+m(y+z)+y)，这时候x+y=(n−2m)(y+z)，因为环的大小是y+z，说明从链表头经过环入口到达相遇地方经过的距离等于整数倍环的大小：那我们从头开始遍历到相遇位置，和从相遇位置开始在环中遍历，会使用相同的步数，而双方最后都会经过入口到相遇位置这y个节点，那说明这y个节点它们就是重叠遍历的，那它们从入口位置就相遇了，这我们不就找到了吗？

图示协助分析：

---

解题步骤：

• step 1：使用BM6.判断链表中是否有环中的方法判断链表是否有环，并找到相遇的节点。
• step 2：慢指针继续在相遇节点，快指针回到链表头，两个指针同步逐个元素逐个元素开始遍历链表。
• step 3：再次相遇的地方就是环的入口。

---

​​​​​​​图示过程解析：

---

代码编写：

---

二、删除链表的倒数第n个节点

题目描述

描述：
给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针。

---

举例说明：
给出的链表为: 1→2→3→4→5, n=2.
删除了链表的倒数第 n 个节点之后,链表变为1→2→3→5.

---

数据范围： 链表长度 0≤�≤10000≤n≤1000，链表中任意节点的值满足 0≤val≤100

要求：空间复杂度 O(1)，时间复杂度 O(n)
备注：题目保证 n一定是有效的;

---

示例1：

---

题目解析

解题思路：

双指针（推荐使用）

思路： 

我们无法逆序遍历链表，就很难得到链表的倒数第n个元素，那我们可以试试反过来考虑，如果当前我们处于倒数第n的位置上，即距离链表尾的距离是n，那我们假设双指针指向这两个位置，二者同步向前移动，当前面个指针到了链表头的时候，两个指针之间的距离还是n。虽然我们没有办法让指针逆向移动，但是我们刚刚这个思路却可以正向实施。

---

解题步骤：

• step 1：给链表添加一个表头，处理删掉第一个元素时比较方便。
• step 2：准备一个快指针，在链表上先走n步。
• step 3：准备慢指针指向原始链表头，代表当前元素，前序节点指向添加的表头，这样两个指针之间相距就是一直都是n。
• step 4：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数n个元素的位置。
• step 5：最后将该节点前序节点的指针指向该节点后一个节点，删掉这个节点。

---

图示过程分析：

---

代码编写：

---

总结