面试题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 的节点。

解题思路

1. 两次遍历: 一次求节点个数 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

2. 双指针

• 第一个指针移动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

3. 递归法

递归往下走，同时增加一个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)

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