返回单向链表倒数第 k 个结点
文章目录
1.问题描述
返回单向链表倒数第 k 个结点（一次遍历）。
示例：
输入： 1->2->3->4->5 和 k = 2
输出： 42.难度等级
easy
3.热门指数
★★★★★
这是一道关于链表的经典面试题。鄙人于 2022 年在虾皮一面时遇到，非常热门，必须掌握。
4.解题思路
前后双指针。前指针先走 k 个结点，后指针再从头结点开始与前指针一起向前移动，直到前指针遍历完链表。此时后指针的位置便是倒数第 k 个结点。
时间复杂度：
O(n)，其中 n 为链表长度，遍历链表需线性 O(n) 时间。
空间复杂度：
O(1)，双指针 pre , cur 使用常数大小的额外空间。
5.实现示例
下面以 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参考文献
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2022-07-19，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录