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

Categories:

Tags:

题目描述
思路分析
1. 解法一：快慢指针（推荐）
相似题目

题目描述

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

思路分析

解法一：快慢指针（推荐）

核心思路：

用两个指针 fast 和 slow 同时指向头节点，让 fast 先走 k 步，然后两者同步前进，当 fast 到达链表末尾（null）时，slow 恰好在倒数第 k 个节点。

推导过程：

链表长度为 n，倒数第 k 个节点是正数第 n-k+1 个

fast 先走 k 步后在第 k+1 个节点，此时 fast 与 slow 相差 k

两者同步走 n-k 步后，fast 到达末尾（null），slow 在第 n-k+1 个节点 ✓

一次遍历，无需获取链表长度。

复杂度分析：

时间复杂度：O(n)，其中 n 为链表长度，fast 指针最多走 n 步

空间复杂度：O(1)，仅使用两个指针

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head, slow = head;
        // fast 先走 k 步
        for (int i = 0; i < k; i++) {
            fast = fast.next;
        }
        // fast 和 slow 同步移动，直到 fast 到达末尾
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

func getKthFromEnd(head *ListNode, k int) *ListNode {
	fast, slow := head, head
	// fast 先走 k 步
	for i := 0; i < k; i++ {
		fast = fast.Next
	}
	// fast 和 slow 同步移动，直到 fast 到达末尾
	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}
	return slow
}

相似题目

题目	难度	考察点
19. 删除链表的倒数第 N 个结点	中等	快慢指针、链表删除
876. 链表的中间结点	简单	快慢指针、找中点
141. 环形链表	简单	快慢指针、判断环
142. 环形链表 II	中等	快慢指针、找环入口
160. 相交链表	简单	双指针、链表相交
234. 回文链表	简单	快慢指针、找中点+反转

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/72487765