输入一个长度为 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