1. 题目

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

给定一个链表: 1->2->3->4->5, 和 k = 2.
返回链表 4->5.

2. 我的解法：遍历两次链表

思路：

第一次遍历链表，获得链表长度；
第二次遍历链表，找到第 length-k 个节点并返回。

code:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:# 第一次遍历链表，获得链表长度length=1tail=headwhile tail:tail=tail.nextlength+=1# 第二次遍历链表，找到第 length-k 个节点并返回start=1while start!=length-k:head=head.nextstart+=1return head

分析：时间复杂度为 O(n)，空间复杂度为 O(1)

3. 更优解法：快慢指针，遍历一次链表

思路：快慢指针

首先让 slow 指向头节点，fast 指向第 k+1 个节点；
然后让 slow 和 fast 同步向后走，当 fast 指向链表的尾部空节点时，返回 slow 即可。

code:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution:def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:# 快慢指针：始终让 fast 指针领先 slow 指针 k 个节点slow=headfast=headfor _ in range(k):fast=fast.next# 当 fast = None 时返回 slowwhile fast:slow=slow.nextfast=fast.nextreturn slow

分析：时间复杂度为 O(n)，空间复杂度为 O(1)