两种方法
1.在链表的初始化数据中加入 num 数据， 每添加一个节点，num加1，每删除一个节点，num减1
查找倒数第k个元素，即 指向第一个节点的指针向后移动 num - k 步。
2.使用两个指针 i 和 j， i和j初始化都指向第一个节点。
查看倒数第k个元素，先将 j 向右移动 k-1 步。
再将 i 和 j 同时向右移动，直到 j 指向最后一个元素结束。
这时候 i 指向的元素即 倒数第k个元素。返回 i 指向节点的值即可。
#!/usr/bin/env python3
# -*- coding: utf-8 -*- class Node(object):
def __init__(self, elem, next_=None):
self.elem = elem
self.next = next_ class Simple_List(object):
def __init__(self):
self.head = None
self.num = 0 def is_empty(self):
return self.head is None def prepend(self, elem):
self.head = Node(elem, self.head)
self.num += 1 def prepop(self):
if self.is_empty():
raise ValueError("List is Empty")
e = self.head.elem
self.head = self.head.next
self.num -= 1
return e def bianli(self):
p = self.head
li = []
while p:
li.append(p.elem)
p = p.next
return li def find_the_key(self, key):
n = self.num - key
p = self.head
while n:
p = p.next
n -= 1
return p.elem def find_the_key1(self,key):
i,j = self.head, self.head
while key-1:
j = j.next
key -= 1
while j.next:
i = i.next
j = j.next
return i.elem if __name__ == "__main__":
sl = Simple_List()
for i in [1,4,8,2,4,8,5]:
sl.prepend(i)
print("链表:",sl.bianli())
key = int(input("查看该链表倒数第k个值:"))
print("倒数第k个值:",sl.find_the_key(key))
print("倒数第k个值:",sl.find_the_key1(key))
之前写这个题目的时候没有注意到边界问题，当用户输入的key值不合理时，会发生错误。
所以我们要对用户输入的数据进行判断并处理。
修改的地方如下，其他地方不变
def find_the_key(self, key):
if key < 1 or key > self.num:
raise ValueError("num must in 0<key<={}".format(self.num))
n = self.num - key
p = self.head
while n:
p = p.next
n -= 1
return p.elem def find_the_key1(self,key):
if key < 1:
raise ValueError("num is unabled,please repeat input")
i,j = self.head, self.head
while key-1:
j = j.next
key -= 1
if j is None:
raise ValueError("num is unabled,please repeat input")
while j.next:
i = i.next
j = j.next
return i.elem