当前位置：首页 > article >正文

【Java 数据结构】面试题 02.02. 返回倒数第 k 个节点

article 2025/3/1 13:00:21

🔥博客主页🔥：【坊钰_CSDN博客】

欢迎各位点赞👍评论✍收藏⭐

1. 题目

2. 解析

2.1 普通方法

2.1 快慢节点方法

3. 代码实现

3.1 普通方法

3.2 快慢节点方法

4. 小结

1. 题目

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意：本题相对原题稍作改动

示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：

给定的 k 保证是有效的。

2. 解析

2.1 普通方法

参考该博客：【Java 数据结构】链表的中间结点-CSDN博客

2.1 快慢节点方法

先让块节点先走 K - 1 步，然后在块节点和慢节点一块走，当块节点到头，慢节点就是目标节点

3. 代码实现

3.1 普通方法

class Solution {
    public int kthToLast(ListNode head, int k) {
        int count = 0;
        ListNode ret = head;
        while (ret != null) {
            count++;
            ret = ret.next;
        }
        count = count - k;
        ret = head;
        while (count != 0) {
            ret = ret.next;
            count--;
        }
        return ret.val;
    }
}

3.2 快慢节点方法

class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        int count = k - 1;
        while (count != 0) {
            fast = fast.next;
            count--;
        }
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}