【面试必刷TOP101】链表中环的入口结点 & 链表中倒数最后k个结点

目录

题目：链表中环的入口结点_牛客题霸_牛客网 (nowcoder.com)

题目的接口：

解题思路：

代码：

过啦！！！

题目：链表中倒数最后k个结点_牛客题霸_牛客网 (nowcoder.com)

题目的接口：

解题思路：

代码：

过啦！！！

写在最后：

---

题目：链表中环的入口结点_牛客题霸_牛客网 (nowcoder.com)

题目的接口：

package main
 
func EntryNodeOfLoop(pHead *ListNode) *ListNode {
    
}

解题思路：

这道题目有一个关键点，我在第一次做的时候是不知道的，但是做过一次之后以后都知道怎么做了，理论上应该是有数学证明的，不过我数学不好，所以不会证明。

关键点：头结点到入口位置的距离 == 快慢指针相交位置到入口位置的距离 根据这个规律编写代码就行了。

代码：

package main
 
func EntryNodeOfLoop(pHead *ListNode) *ListNode {
    fast := pHead
    slow := pHead
 
    // 找到快慢指针相交的位置
    for fast != nil && fast.Next != nil {
        fast = fast.Next.Next
        slow = slow.Next
        if fast == slow {
            break
        }
    }
 
    // 头结点到入口位置的距离 == 快慢指针相交位置到入口位置的距离
    for fast != nil && pHead != nil && pHead.Next != nil {
        if fast == pHead {
            return fast
        }
        fast = fast.Next
        pHead = pHead.Next
    }
    
    return nil
}

过啦！！！

题目：链表中倒数最后k个结点_牛客题霸_牛客网 (nowcoder.com)

题目的接口：

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */
 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类 
*/
func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {
    // write code here
}

解题思路：

这道题目我第一眼看到，其实想到的是暴力解法，先暴力遍历一下链表的长度，然后再根据 k 的长度来把倒数 k 个节点都给截取出来，但是暴力肯定不是最优解，所以就开始思考怎么优化，

比较简答的一个优化思路就是快慢指针，核心思路：让 fast 指针先走 k 步，再让两个指针一起往后走，当 fast 指针走到 nil 的时候，slow 指针就在倒数第 k 个位置上了，因为 fast 指针和 slow 指针他们相距 k 个位置。

代码：

package main
import . "nc_tools"
/*
 * type ListNode struct{
 *   Val int
 *   Next *ListNode
 * }
 */
 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead ListNode类 
 * @param k int整型 
 * @return ListNode类 
*/
func FindKthToTail( pHead *ListNode ,  k int ) *ListNode {
    fast := pHead
    slow := pHead
 
    for i := 0; i < k; i++ {
        if fast == nil {
            return nil
        }
        fast = fast.Next
    }
 
    for fast != nil {
        fast = fast.Next
        slow = slow.Next
    }
 
    return slow
}

过啦！！！

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~