面试题 02.02. 返回倒数第 k 个节点

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

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

示例：

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

说明：

给定的 k 保证是有效的。

快慢指针

快指针先走k步，到达第k+1个节点，快指针到达空节点时距离倒数第k个节点正好k步。因此慢指针指向倒数第k个节点。

class Solution {
    public int kthToLast(ListNode head, int k) {
        ListNode pre = head, cur = head;
        // 快指针先走k步，到达第k+1个节点
        for (int i = 0; i < k; i++) cur = cur.next;
        
        // 快指针到达空节点时距离倒数第k个节点正好k步。因此慢指针指向倒数第k个节点
        while (cur != null) {
            pre = pre.next;
            cur = cur.next;
        }
        
        return pre.val;
    }
}

• 时间复杂度 O(N) ： 其中 N 为链表长度；遍历链表使用线性 O(N) 时间。
• 空间复杂度 O(1) ： 双指针 pre , cur 使用常数大小的额外空间。