【leetcode】剑指 Offer 22. 链表中倒数第k个节点（lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof）（双指针）[简单]

2023-05-16

链接

https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/

耗时

解题：7 min
题解：3 min

题意

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

思路

快慢指针，快指针先向后移动 k 次，然后快慢指针同时移动，当快指针到达链表末尾的空节点时，慢指针正好指向倒数第 k 个节点。

时间复杂度： O ( n ) O(n) O(n)

AC代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        ListNode* fast = head;
        ListNode* slow = head;
        for(int i = 0; i < k; ++i) {
            fast = fast->next;
        }
        while(fast != NULL) {
            fast = fast->next;
            slow = slow->next; 
        }
        return slow;
    }
};

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

【leetcode】剑指 Offer 22. 链表中倒数第k个节点（lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof）（双指针）[简单] 的相关文章

【leetcode】392. 判断子序列（is-subsequence）（贪心）[简单]

链接 https leetcode cn com problems is subsequence 耗时解题 xff1a 17 min 题解 xff1a 9 min 题意给定字符串 s 和 t xff0c 判断 s 是否为 t 的子序列
【leetcode】104. 二叉树的最大深度（maximum-depth-of-binary-tree）（DFS）[简单]

链接 https leetcode cn com problems maximum depth of binary tree 耗时解题 xff1a 7 min 题解 xff1a 3 min 题意给定一个二叉树 xff0c 找出其最大深度
shell脚本--三种引号的区别

shell脚本中 xff0c 三种引号分别为 xff1a 单引号 39 39 xff0c 双引号 34 34 xff0c 反引号 96 96 xff0c 反引号就是键盘esc下面的那个键 1 单引号 xff1a 在单引号之间的内容 xff0
【leetcode】343. 整数拆分（integer-break）（DP）[中等]

链接 https leetcode cn com problems integer break 耗时解题 xff1a 19 min 题解 xff1a 18 min 题意给定一个正整数 n xff0c 将其拆分为至少两个正整数的和 x
【leetcode】面试题 08.03. 魔术索引（magic-index-lcci）（二分）[简单]

链接 https leetcode cn com problems magic index lcci 耗时解题 xff1a 40 min 题解 xff1a 21 min 题意魔术索引在数组A 0 n 1 中 xff0c 有所谓的魔术索
【leetcode】207. 课程表（course-schedule）（拓扑排序）[中等]

链接 https leetcode cn com problems course schedule 耗时解题 xff1a 32 min 题解 xff1a 10 min 题意你这个学期必须选修 numCourse 门课程 xff0c 记为
【leetcode】100. 相同的树（same-tree）（DFS）[简单]

链接 https leetcode cn com problems same tree 耗时解题 xff1a 8 min 题解 xff1a 5 min 题意给定两个二叉树 xff0c 编写一个函数来检验它们是否相同如果两个树在结构上相
【leetcode】133. 克隆图（clone-graph）（BFS）[中等]

链接 https leetcode cn com problems clone graph 耗时解题 xff1a 0 5 day 题解 xff1a 13 min 题意给你无向连通图中一个节点的引用 xff0c 请你返回该图的深拷贝
【leetcode】20. 有效的括号（valid-parentheses）（堆栈）[简单]

链接 https leetcode cn com problems valid parentheses 耗时解题 xff1a 18 h 题解 xff1a 5 min 题意给定一个只包括 xff0c xff0c xff0c xff0c x
【leetcode】733. 图像渲染（flood-fill）（BFS）[简单]

链接 https leetcode cn com problems flood fill 耗时解题 xff1a 37 min 题解 xff1a 5 min 题意有一幅以二维整数数组表示的图画 xff0c 每一个整数表示该图画的像素值大小
【leetcode】110. 平衡二叉树（balanced-binary-tree）（DFS）[简单]

链接 https leetcode cn com problems balanced binary tree 耗时解题 xff1a 28 min 题解 xff1a 7 min 题意给定一个二叉树 xff0c 判断它是否是高度平衡的二叉树
【leetcode】109. 有序链表转换二叉搜索树（convert-sorted-list-to-binary-search-tree）（DFS）[中等]

链接 https leetcode cn com problems convert sorted list to binary search tree 耗时解题 xff1a 44 min 题解 xff1a 15 min 题意给定一个单链
【leetcode】111. 二叉树的最小深度（minimum-depth-of-binary-tree）（BFS）[简单]

链接 https leetcode cn com problems minimum depth of binary tree 耗时解题 xff1a 12 min 题解 xff1a 3 min 题意给定一个二叉树 xff0c 找出其最小深
shell脚本--let、expr、bc、scale的用法

xff08 1 xff09 let bin bash let控制循环流程 i 61 1 n 61 10 while i lt 61 n do echo i let i 43 43 done xff08 2 xff09 expr bin ba
【leetcode】201. 数字范围按位与（bitwise-and-of-numbers-range）（位运算）[中等]

链接 https leetcode cn com problems bitwise and of numbers range 耗时解题 xff1a 1 h 21 min 题解 xff1a 28 min 题意给定范围 m n xff0c
【leetcode】459. 重复的子字符串（repeated-substring-pattern）（字符串）[简单]

链接 https leetcode cn com problems repeated substring pattern 耗时解题 xff1a 27 min 题解 xff1a 4 min 题意给定一个非空的字符串 xff0c 判断它是否
【leetcode】841. 钥匙和房间（keys-and-rooms）（BFS）[中等]

链接 https leetcode cn com problems keys and rooms 耗时解题 xff1a 20 min 题解 xff1a 2 min 题意有 N 个房间 xff0c 开始时你位于 0 号房间每个房间有不同
【leetcode】107. 二叉树的层次遍历 II（binary-tree-level-order-traversal-ii）（BFS）[简单]

链接 https leetcode cn com problems binary tree level order traversal ii 耗时解题 xff1a 20 min 题解 xff1a 2 min 题意给定一个二叉树 xff0
【leetcode】leetRepo histogram
【leetcode】39. 组合总和（combination-sum）（回溯）[中等]

链接 https leetcode cn com problems combination sum 耗时解题 xff1a xff1f min xff08 下次补上 xff09 题解 xff1a 10 min 题意给定一个无重复元素的数组

随机推荐

【leetcode】40. 组合总和 II（combination-sum-ii）（回溯）[中等]

链接 https leetcode cn com problems combination sum ii 耗时解题 xff1a 26 min 题解 xff1a 18 min 题意给定一个数组 candidates 和一个目标数 targ
shell脚本--while read line循环

while read line循环可以按行读入 xff0c 一直到所有行读完才退出循环在实际工作中 xff0c 经常采用这种循环进行数据处理 bin bash 测试 while read line 循环的使用循环读取一个ip文件的每一行
【leetcode】79. 单词搜索（word-search）（回溯）[中等]

链接 https leetcode cn com problems word search 耗时解题 xff1a 50 min 题解 xff1a 6 min 题意给定一个二维网格和一个单词 xff0c 找出该单词是否存在于网格中单词必
【leetcode】94. 二叉树的中序遍历（binary-tree-inorder-traversal）（dfs）[中等]

链接 https leetcode cn com problems binary tree inorder traversal 耗时解题 xff1a 18 min 题解 xff1a 1 min 题意给定一个二叉树 xff0c 返回它的中
【leetcode】37. 解数独（sudoku-solver）（回溯）[困难]

链接 https leetcode cn com problems sudoku solver 耗时解题 xff1a 2 h 30 min 题解 xff1a 14 min 题意编写一个程序 xff0c 通过已填充的空格来解决数独问题一
【leetcode】226. 翻转二叉树（invert-binary-tree）（dfs）[简单]

链接 https leetcode cn com problems invert binary tree 耗时解题 xff1a 5 min 题解 xff1a 11 min 题意翻转一棵二叉树 4 2 7 1 3 6 9 gt 4 7 2
【leetcode】685. 冗余连接 II（redundant-connection-ii）（dfs）[困难]

链接 https leetcode cn com problems redundant connection ii 耗时解题 xff1a 1 h 51 min 题解 xff1a 22 min 题意在本问题中 xff0c 有根树指满足以下
【leetcode】47. 全排列 II（permutations-ii）（回溯）[中等]

链接 https leetcode cn com problems permutations ii 耗时解题 xff1a 24 min 题解 xff1a 17 min 题意给定一个可包含重复数字的序列 xff0c 返回所有不重复的全排列
【leetcode】404. 左叶子之和（sum-of-left-leaves）（dfs）[简单]

链接 https leetcode cn com problems sum of left leaves 耗时解题 xff1a 20 min 题解 xff1a 6 min 题意计算给定二叉树的所有左叶子之和思路 dfs 到的每个节点
【leetcode】78. 子集（subsets）（位运算）[中等]

链接 https leetcode cn com problems subsets 耗时解题 xff1a 10 min 题解 xff1a 19 min 题意给定一组不含重复元素的整数数组 nums xff0c 返回该数组所有可能的子
【leetcode】538. 把二叉搜索树转换为累加树（convert-bst-to-greater-tree）（回溯）[简单]

链接 https leetcode cn com problems convert bst to greater tree 耗时解题 xff1a 10 min 题解 xff1a 14 min 题意给定一个二叉搜索树 xff08 Bina
Linux服务管理--VSFTP服务--openssl+vsftpd加密验证方式

openssl 43 vsftpd 加密验证方式拓展 xff1a 使用tcpdump 工具进行指定端口抓包 xff0c 抓取ftp登录过程中的数据包 tcpdump i eth0 nn X vv tcp port 21 and ip ho
【leetcode】617. 合并二叉树（merge-two-binary-trees）（dfs）[简单]

链接 https leetcode cn com problems merge two binary trees 耗时解题 xff1a 25 min 题解 xff1a 5 min 题意给定两个二叉树 xff0c 想象当你将它们中的一个覆
【Linux】Win10、Ubuntu 双系统安装后BIOS都有启动项并且都能分别进入，但没有引导界面

问题 xff1a Ubuntu Win10 双系统安装后BIOS都有启动项并且都能分别进入 xff0c 但没有引导原因 xff1a 一种情况是如下图所示 xff0c BIOS 是 UEFI xff0c 但是安装 Ubuntu 时 xff0
【leetcode】113. 路径总和 II（path-sum-ii）（dfs）[中等]

链接 https leetcode cn com problems path sum ii 耗时解题 xff1a 31 min 题解 xff1a 10 min 题意给定一个二叉树和一个目标和 xff0c 找到所有从根节点到叶子节点路径总
【leetcode】117. 填充每个节点的下一个右侧节点指针 II（populating-next-right-pointers-in-each-node-ii）（bfs）[中等]

链接 https leetcode cn com problems populating next right pointers in each node ii 耗时解题 xff1a 12 min 题解 xff1a 4 min 题意给定
【leetcode】701. 二叉搜索树中的插入操作（insert-into-a-binary-search-tree）（dfs）[中等]

链接 https leetcode cn com problems insert into a binary search tree 耗时解题 xff1a 21 min 题解 xff1a 6 min 题意给定二叉搜索树 xff08 BS
【leetcode】LCP 19. 秋叶收藏集（UlBDOe）（DP）[中等]

链接 https leetcode cn com problems UlBDOe 耗时解题 xff1a 3 h 15 min 题解 xff1a 58 min 题意小扣出去秋游 xff0c 途中收集了一些红叶和黄叶 xff0c 他利用这些
【leetcode】70. 爬楼梯（climbing-stairs）（DP）[简单]

链接 https leetcode cn com problems climbing stairs 耗时解题 xff1a 5 min 题解 xff1a 12 min 题意假设你正在爬楼梯需要 n 阶你才能到达楼顶每次你可以爬 1 或
【leetcode】剑指 Offer 22. 链表中倒数第k个节点（lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof）（双指针）[简单]

链接 https leetcode cn com problems lian biao zhong dao shu di kge jie dian lcof 耗时解题 xff1a 7 min 题解 xff1a 3 min 题意输入一个链

【leetcode】剑指 Offer 22. 链表中倒数第k个节点（lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof）（双指针）[简单]

链接

耗时

题意

思路

AC代码

【leetcode】剑指 Offer 22. 链表中倒数第k个节点（lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof）（双指针）[简单] 的相关文章

随机推荐

热门标签