程序员面试金典 - 面试题 02.02. 返回倒数第 k 个节点

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

示例：

• 输入： 1->2->3->4->5 和 k = 2
• 输出： 4

说明：

给定的 k 保证是有效的。

题目思考

1. 如何优化时间复杂度?

解决方案

思路

• 一个很自然的想法是先遍历一遍整个链表, 统计节点数目 n, 然后再从头开始, 遍历到第 n-k 个节点即为所求
• 但是上面做法需要遍历 n+(n-k) 个节点, 时间复杂度是 O(N+N-K), 效率不够高, 有没有办法只遍历 n 个节点就得出结果呢?
• 答案也是有的, 我们可以利用双指针的思路, 使用一快一慢两个指针:
  • 快指针先遍历到第 k 个节点, 这个过程中慢指针不动
  • 然后慢指针再出发, 此时快慢指针每次都后移一位, 直到快指针达到终点, 显然此时慢指针指向的位置就是第 n-k 个节点
• 利用这个优化, 时间复杂度就降低到了 O(N)

复杂度

• 时间复杂度 O(N): 需要一次遍历所有节点
• 空间复杂度 O(1): 只使用了几个常数空间的变量

代码

class Solution:
    def kthToLast(self, head: ListNode, k: int) -> int:
        # 快慢指针
        fast = head
        slow = head
        for _ in range(k):
            # 快指针先走k步, 慢指针不动
            fast = fast.next
        # 然后两者再一起走
        while fast:
            fast = fast.next
            slow = slow.next
        return slow.val

大家可以在下面这些地方找到我~😊

我的知乎专栏

我的头条号

我的 CSDN

我的 Leetcode

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊