剑指Offer之面试题22：链表中倒数第k个节点

面试题22：链表中倒数第k个节点

每日一句： “Successful people appear to be traveling along one continual, successful road. — G. Kingsley Ward

输入一个链表，输出该链表中倒数第 k 个节点。为了符合大多数人的习惯，本题从 1 开始计数，即链表的尾节点是倒数第 1 个节点。例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

解题思路

两次遍历: 一次求节点个数 n，一次走 n-k+1 步

单链表是单向，所以只能顺着数，但是如果要找到倒数第 *k* 个节点，其实就是顺着数第 *n - k + 1* 个节点。
时间复杂度: $O(2n)$
空间复杂度：$O(1)$

class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
cur,count = head, 0 # 这里一定要保存head的位置
while head:
count += 1
head = head.next # 第一次遍历结束后，head为空

for _ in range(count - k):
cur = cur.next # 使用cur来重新遍历
return cur

双指针

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

时间复杂度: $O(n)$

class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:

if head is None or k <= 0:
return None

first, second = head, head

# first一直走到k
for _ in range(k):
first = first.next
# 当first不为空，first,second一起走
while first:
first, second = first.next, second.next
# first为空，second所在的位置刚好就是倒数第k个节点
return second

递归法

递归往下走，同时增加一个​​count​​来记录递的次数，并把结果记录在res中，当到达第k个节点时，直接返回​​head​​

class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:

count = 0
def helper(head):
# 边界条件
if head is None:
return None
nonlocal count
res = helper(head.next)
count += 1
if count == k:
return head
return res
return helper(head)

其实也不需要增加 count，直接利用 k，每一次递的过程中，对 k 进行减一，当 ​​k==0​​ ,说明到达第 k 个节点，返回 ​​head​​ ,不然将继续进行下去，直到 ​​head​​ 为空。

class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:

def helper(head):
if head is None:
return None
nonlocal k
res = helper(head.next)
k -= 1
if k == 0:
return head
return res
return helper(head)

这里是宇宙之一粟，下次见