链表中倒数最后k个结点

链表中倒数最后k个结点_牛客题霸_牛客网

问题简述

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。
如果该链表长度小于k，请返回一个长度为 0 的链表。

思路1

• 先计算链表长度 L，再重新走 L-k 步；

Python

class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        
        L = 0
        cur = pHead
        while cur:
            cur = cur.next
            L += 1
        
        cur = pHead
        d = L - k
        while d and cur:
            cur = cur.next
            d -= 1
        
        return cur

思路2：快慢指针

• 快指针先走 k 步；最后返回慢指针；

Python

class Solution:
    def FindKthToTail(self , pHead: ListNode, k: int) -> ListNode:
        
        f, s = pHead, pHead
        # 快指针先走 k 步
        for _ in range(k):
            if not f:
                return f
            f = f.next
        
        while f:
            f = f.next
            s = s.next
        
        return s