剑指 Offer:22. 链表中倒数第k个节点

简介: 剑指 Offer:22. 链表中倒数第k个节点

1. 题目

剑指 Offer 22. 链表中倒数第k个节点


2. 描述

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


示例:


给定一个链表: 1->2->3->4->5, 和 k = 2.


返回链表 4->5.


3. 实现方法

3.1 方法 1

3.1.1 思路

设有两个指针 fast, slow 指向 head;

先将 fast 向后移动 k 次,此时 fast,slow 的距离为 k;

接着同时移动 fast,slow 直到 fast 指向 null;

此时slow 即为答案;

3.1.2 实现


public ListNode getKthFromEnd(ListNode head, int k) {
    //初始化两个指针均指向 head
    ListNode slow = head;
    ListNode fast = head;
    // 将快指针向后移动 k 次
    for(int i = 0; i < k; i++){
        fast = fast.next;
    }
    // 同时移动快慢指针,直到快指针指向 null
    while(fast != null){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}
目录
相关文章
|
3月前
|
机器学习/深度学习 算法
24. 两两交换链表中的节点, 19.删除链表的倒数第N个节点 ,面试题 02.07. 链表相交
1. **两两交换链表中的节点**:通过引入虚拟头结点,使所有节点都能采用统一的交换逻辑,避免对头结点单独处理。 2. **删除链表的倒数第N个节点**:利用双指针技巧,让快慢指针保持N个节点的距离,当快指针到达末尾时,慢指针正好指向待删除节点的前一个节点。 3. **链表相交**:先计算两链表长度并调整起点,确保从相同距离末尾的位置开始遍历,从而高效找到相交节点或确定无交点。 以上方法均在时间复杂度和空间复杂度上进行了优化,适合用于理解和掌握链表的基本操作及常见算法设计思路。
|
11月前
|
算法
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
【❤️算法笔记❤️】-每日一刷-19、删除链表的倒数第 N个结点
179 1
|
11月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
121 0
LeetCode第二十四题(两两交换链表中的节点)
|
11月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
125 0
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
100 0
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
131 2
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
167 1
[leetcode 链表] 反转链表 vs 链表相交
[leetcode 链表] 反转链表 vs 链表相交