“Successful people appear to be traveling along one continual, successful road. What is not apparent is the perseverance it takes following each defeat to keep you on that road. No one I know of has ever experienced one success after another without defeats, failures, disappointments, and frustrations galore along the way. Learning to overcome those times of agony is what separates the winners from the losers.” — G. Kingsley Ward

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

输入一个链表，输出该链表中倒数第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)

人生苦短，继续使用Python刷题。宇宙之一粟，下次见