2009 年第 42 题

题目描述

已知一个带表头结点的单链表，只给出头指针 list。请设计一个尽可能高效的算法，查找链表中倒数第 k 个位置上的结点；若查找成功，输出该结点的 data 值并返回 1，否则返回 0。

解题思路

核心做法是双指针。

1. 先让快指针从首元结点开始先走 k 步。
2. 如果不到 k 步链表就结束，说明 k 非法，直接返回失败。
3. 然后让快慢指针同时向后移动。
4. 当快指针走到表尾时，慢指针刚好停在倒数第 k 个结点。

这样只遍历链表一次，不需要先求链表长度。

手算示例

链表：head -> 1 -> 2 -> 3 -> 4 -> 5，k = 2

先让 fast 走 2 步：
fast: 1 -> 2
slow: 1

然后一起走：
fast=3, slow=2
fast=4, slow=3
fast=5, slow=4
fast 到尾后结束

答案：slow 指向 4，即倒数第 2 个结点

Python 实现

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def find_kth_from_end_with_head(head: ListNode, k: int):
    """
    head 是带表头结点的链表头指针。
    返回 (是否成功, 结点值或 None)
    """
    if head is None or k <= 0:
        return 0, None

    fast = head.next
    slow = head.next

    for _ in range(k):
        if fast is None:
            return 0, None
        fast = fast.next

    while fast is not None:
        fast = fast.next
        slow = slow.next

    return 1, slow.val

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

易错点

• 真题是带表头结点的链表，head 本身不是有效数据结点。
• k <= 0 或 k 大于链表长度时都应返回失败。
• 快指针先走的是 k 步，不是 k - 1 步。

对应题

来源	题目	相似度	主要差异
LeetCode	19. 删除链表的倒数第 N 个结点	90%	真题只要求查找，不要求删除
剑指 Offer	22. 链表中倒数第 k 个结点	90%	真题为带表头结点链表

难度

⭐️⭐️