返回单向链表倒数第 k 个结点(一次遍历)。
示例:
输入: 1->2->3->4->5 和 k = 2
输出: 4
easy
★★★★★
这是一道关于链表的经典面试题。鄙人于 2022 年在虾皮一面时遇到,非常热门,必须掌握。
前后双指针。前指针先走 k 个结点,后指针再从头结点开始与前指针一起向前移动,直到前指针遍历完链表。此时后指针的位置便是倒数第 k 个结点。
时间复杂度:
O(n),其中 n 为链表长度,遍历链表需线性 O(n) 时间。
空间复杂度:
O(1),双指针 pre , cur 使用常数大小的额外空间。
下面以 Golang 为例,给出实现示例。
type ListNode struct {
v int
next *ListNode
}
// kthToLast 返回单向链表倒数第 k 个结点。
func kthToLast(head *ListNode, k int) *ListNode {
pre, cur := head, head
var n int
for pre != nil {
n++
pre = pre.next
if n > k {
cur = cur.next
}
}
return cur
}
验证:
func main() {
// 创建链表 1->2->3->4->5。
head := &ListNode{v: 1}
cur := head
for i := 2; i <= 5; i++ {
cur.next = &ListNode{v: i}
cur = cur.next
}
// 返回单向链表倒数第 1 个结点(5)。
node := kthToLast(head, 1)
fmt.Println(node.v)
// 返回单向链表倒数第 2 个结点(4)。
node = kthToLast(head, 2)
fmt.Println(node.v)
// 返回单向链表倒数第 3 个结点(3)。
node = kthToLast(head, 3)
fmt.Println(node.v)
}
输出:
5
4
3