#初始化鏈表的結(jié)點(diǎn)
class Node():
  def __init__(self,item):
    self.item = item
    self.next = None
#傳入頭結(jié)點(diǎn)，獲取整個(gè)鏈表的長(zhǎng)度
def length(headNode):
  if headNode == None:
    return None
  count = 0
  currentNode =headNode
  #嘗試了一下帶有環(huán)的鏈表，計(jì)算長(zhǎng)度是否會(huì)死循環(huán)，確實(shí)如此，故加上了count限制 = =||
  while currentNode != None and count <=1000:
    count+=1
    currentNode = currentNode.next
  return count
#獲取倒數(shù)第K個(gè)結(jié)點(diǎn)的值，傳入頭結(jié)點(diǎn)和k值
def findrKnode(head,k):
  if head == None:
    return None
  #如果長(zhǎng)度小于倒數(shù)第K個(gè)值,則返回通知沒(méi)有這么長(zhǎng)
  elif length(head)<k:
    print("鏈表長(zhǎng)度沒(méi)有倒數(shù)第"+str(k)+"數(shù)")
    return None
  else:
    #設(shè)置兩個(gè)針，一個(gè)快，一個(gè)慢，都指向頭結(jié)點(diǎn)
    fastPr = head
    lowPr = head
    count = 0
    #讓fastPr先走k個(gè)長(zhǎng)度
    while fastPr!=None and count<k:
      count+=1
      fastPr = fastPr.next
    #此時(shí)fastPr和lowPr同速前進(jìn)，當(dāng)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)