Skip to content

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

Open
@Geekhyt

Description

@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)

Metadata

Metadata

Assignees

No one assigned

    Labels

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions