如何解答输入一个链表，输出该链表中倒数第 k 个结点这个问题，可以采用以下方法：
如何解答输入一个链表，输出该链表中倒数第 k 个结点这个问题，可以采用以下方法：
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. 双指针
时间复杂度: $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)
复制代码
评论