14 链表中倒数第k个结点

题目描述

输入一个链表，输出该链表中倒数第k个结点。如果链表长度小于k，返回None。

示例：

链表: 1->2->3->4->5
k=1, 输出: 5
k=2, 输出: 4
k=5, 输出: 1
k=6, 输出: None

解题思路

核心思想：使用双指针（快慢指针）。

关键步骤：

1. 快指针先走k步
2. 如果快指针走到None，说明链表长度<k，返回None
3. 快慢指针同时走，直到快指针走到末尾
4. 慢指针指向的就是倒数第k个结点

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

Python 实现

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


def find_kth_to_tail(head, k):
    """
    找到链表中倒数第k个结点

    Args:
        head: 链表头结点
        k: 倒数第k个

    Returns:
        ListNode: 倒数第k个结点，不存在返回None
    """
    if not head or k <= 0:
        return None

    fast = slow = head

    # 快指针先走k步
    for _ in range(k):
        if not slow:
            return None
        slow = slow.next

    # 快慢指针同时走
    while slow:
        fast = fast.next
        slow = slow.next

    return fast


# 辅助函数：创建链表
def create_linked_list(arr):
    if not arr:
        return None
    head = ListNode(arr[0])
    p = head
    for val in arr[1:]:
        p.next = ListNode(val)
        p = p.next
    return head


# 辅助函数：打印链表
def print_list(head):
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print('->'.join(result))


# 测试代码
if __name__ == "__main__":
    # 创建链表 1->2->3->4->5
    head = create_linked_list([1, 2, 3, 4, 5])
    print("链表: ", end="")
    print_list(head)

    test_cases = [1, 2, 5, 6, 0]

    for k in test_cases:
        result = find_kth_to_tail(head, k)
        if result:
            print(f"倒数第{k}个: {result.val}")
        else:
            print(f"倒数第{k}个: None")

# 输出:
# 链表: 1->2->3->4->5
# 倒数第1个: 5
# 倒数第2个: 4
# 倒数第5个: 1
# 倒数第6个: None
# 倒数第0个: None

图解

双指针法示例: 链表 1->2->3->4->5, k=2

初始状态:
head→1→2→3→4→5→None
     ↑
    fast/slow

步骤1: 快指针先走k=2步
head→1→2→3→4→5→None
     ↑  ↑
    fast slow

步骤2: 快慢指针同时走
head→1→2→3→4→5→None
        ↑  ↑
       fast slow

head→1→2→3→4→5→None
           ↑  ↑
          fast slow

head→1→2→3→4→5→None
              ↑  ↑
             fast slow

步骤3: slow=None，fast指向倒数第2个结点
返回: fast → 结点4