leetCode Middle sword finger Offer The first 22 topic Last in the list k Nodes
link ：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
Enter a linked list , Output the last number in the list k Nodes . In order to conform to the habits of most people , From 1 Start counting , That is, the tail node of the list is the last 1 Nodes .
for example , A list has 6 Nodes , Start from the beginning , Their values, in turn, are 1、2、3、4、5、6. The last of the list 3 Each node has a value of 4 The node of .
Example ：
Given a linked list : 1->2->3->4->5, and k = 2.
Back to the list 4->5.
In the example , Last but not least 2 The nodes are 4, Last but not least 2 It's in order 4, It's easy to see the penultimate k individual , It's in order n-k+1 individual
Then the best way to think of is to traverse the linked list to calculate the length , Then set the counter to find the node .
------------------------
Optimize on this , utilize hash surface , When calculating the length of the linked list , Store subscripts And corresponding nodes , And then directly hash The index subscript in the table finds the node .
----------------
Further optimization , Use double pointer （ Speed pointer ）, stay n-k+1 In this formula , It's written in n-(k-1), Can find inspiration , That is, the fast pointer should be faster than the slow pointer （k-1） Nodes reach the end . So we can make the fast pointer move first k-1 Step , And then the hands go together , When the fast pointer reaches the end , The slow pointer just reaches the penultimate k individual .
class Solution:
def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
if k <= 0 or head == None:
return None
temp = head
kth = head
for i in range(1,k):
if temp != None:
temp = temp.next
while temp.next != None:
temp = temp.next
kth = kth.next
if kth != None:
return kth
return None
