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

[Geekhyt]

原题链接

双指针

1. 在头节点分别定义快、慢两个指针，在定义 n 计数器
2. 快指针先行，直到与慢指针相差 k 时，慢指针也开始走
3. 这样的话，当快指针遍历完成时，慢指针就刚好在倒数第 k 个值的位置了

const kthToLast = function (head, k) {
    let fast = head
    let low = head
    let n = 0
    while (fast) {
        fast = fast.next
        if (n >= k) {
            low = low.next
        }
        n++
    }
    return low.val
}

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