22.md

链表中倒数最后k个结点

题目

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。 如果该链表长度小于k，请返回一个长度为 0 的链表。

要求：空间复杂度 O(n)，时间复杂度 O(n) 进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例

输入：{1,2,3,4,5},2

返回值：{4,5}

说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。

思路

快慢指针

• 第一个指针先移动k步
• 然后第二个指针再从头开始
• 这个时候这两个指针同时移动
• 当第一个指针到链表的末尾的时候
• 返回第二个指针即可

实现

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

// 链表中倒数最后k个结点
func main() {
	var pHead *ListNode
	for _, v := range [5]int{5, 4, 3, 2, 1} {
		node := ListNode{
			Val:  v,
			Next: pHead,
		}
		pHead = &node
	}
	FindKthToTail(pHead, 2)
}

func FindKthToTail(pHead *ListNode, k int) *ListNode {
	var fast *ListNode = pHead
	var slow *ListNode = pHead
	for i := 0; i < k; i++ {
		if fast == nil {
			var empty *ListNode
			return empty
		}
		fast = fast.Next
	}
	for fast != nil {
		fast = fast.Next
		slow = slow.Next
	}
	return slow
}