#初始化鏈表的結點
class Node():
  def __init__(self,item):
    self.item = item
    self.next = None
#傳入頭結點，獲取整個鏈表的長度
def length(headNode):
  if headNode == None:
    return None
  count = 0
  currentNode =headNode
  #嘗試了一下帶有環(huán)的鏈表，計算長度是否會死循環(huán)，確實如此，故加上了count限制 = =||
  while currentNode != None and count <=1000:
    count+=1
    currentNode = currentNode.next
  return count
#獲取倒數(shù)第K個結點的值，傳入頭結點和k值
def findrKnode(head,k):
  if head == None:
    return None
  #如果長度小于倒數(shù)第K個值,則返回通知沒有這么長
  elif length(head)<k:
    print("鏈表長度沒有倒數(shù)第"+str(k)+"數(shù)")
    return None
  else:
    #設置兩個針，一個快，一個慢，都指向頭結點
    fastPr = head
    lowPr = head
    count = 0
    #讓fastPr先走k個長度
    while fastPr!=None and count<k:
      count+=1
      fastPr = fastPr.next
    #此時fastPr和lowPr同速前進，當fastPr走到尾部，lowPr此處的值正好為倒數(shù)的k值
    while fastPr !=None:
      fastPr = fastPr.next
      lowPr = lowPr.next
    return lowPr
if __name__ == "__main__":
  node1 = Node(1)
  node2 = Node(2)
  node3 = Node(3)
  node4 = Node(4)
  node5 = Node(5)
  node6 = Node(6)
  node7 = Node(7)
  node8 = Node(8)
  node9 = Node(9)
  node10 = Node(10)
  node1.next = node2
  node2.next = node3
  node3.next = node4
  node4.next = node5
  node5.next = node6
  node6.next = node7
  node7.next = node8
  node8.next = node9
  node9.next = node10
  print(findrKnode(node1,5).item)