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

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

题目:链表中环的入口结点_牛客题霸_牛客网 (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
}

过啦!!!

写在最后:

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

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

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

相关文章
|
3天前
|
算法
LeetCode第19题删除链表的倒数第 N 个结点
该文章介绍了 LeetCode 第 19 题删除链表的倒数第 N 个结点的解法,通过使用快慢双指针,先将快指针移动 n 步,然后快慢指针一起遍历,直到快指针到达链尾,从而找到倒数第 N 个结点的前一个结点进行删除,同时总结了快慢指针可减少链表遍历次数的特点。
LeetCode第19题删除链表的倒数第 N 个结点
|
1月前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
23 1
【数据结构OJ题】链表中倒数第k个结点
|
5天前
【刷题记录】链表的中间结点
【刷题记录】链表的中间结点
|
1月前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
17 0
【数据结构OJ题】链表的中间结点
|
2月前
|
算法
19.删除链表的倒数第N个结点
19.删除链表的倒数第N个结点
|
1月前
|
机器学习/深度学习 存储
sdut pta 链表3(优化)-----7-3 sdut-C语言实验-链表的结点插入
sdut pta 链表3(优化)-----7-3 sdut-C语言实验-链表的结点插入
13 0
|
2月前
|
算法 C语言
【数据结构与算法 刷题系列】求链表的中间结点
【数据结构与算法 刷题系列】求链表的中间结点
|
2月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
2月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
2月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
17 2