Python实现环形链表详解

这篇文章主要为大家详细介绍了Python实现环形链表，文中示例代码介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下

本文实例为大家分享了Python实现环形链表的具体代码，供大家参考，具体内容如下

我们将单向链表的最后一个节点的指针指向链表的头部（第一个节点），那么就形成了一个环形链表。环形节点可以从任意节点开始遍历其他的节点。

这里主要实现了环形链表节点的遍历、添加、插入、删除，反转。

代码如下：

class Player:"""节点类"""def __init__(self):"""初始化姓名，分数，指针"""self.name = ''self.score = 0self.next = Nonedef ergodic(head, num=None, is_print=False):"""遍历函数，num是遍历到哪一个位置序号，is_print是否触发打印方法"""if head.next is None:return Noneptr = headcount = 0while True:count += 1if is_print:print('No.'+str(count), ptr.name, ptr.score, '--->', ptr.next.name)if count == num:breakif ptr.next == head:breakptr = ptr.nextreturn ptr  # 返回遍历完成后的最后一个节点def invert(x):  # x是链表的第一个节点"""反转环形链表"""y = x.next  # y是x原来的nextx.next = ergodic(x)  # 将第一个节点的next指向最后一个节点(因为反转了)while True:  # 循环反转后面的所有节点r = y.nexty.next = xif r == head:  # r是head说明y已经是原本链表的最后一个节点了return y  # 返回y，这个y是反转后的链表的第一个节点x = yy = rhead = Player()
ptr = headwhile True:select = input("(1).新增   (2).查看   (3).插入   (4).删除   (5).反转   (6).离开\n输入：")if select == "1":  # 新增节点ptr = ergodic(head)  # 获取当前链表最后一个节点if ptr is None:  # ptr为None说明当前在添加第一个节点headhead.name = input("姓名：")head.score = input("分数：")head.next = headelse:  # 添加第一个节点之后的节点next_data = Player()next_data.name = input("姓名：")next_data.score = input("分数：")next_data.next = headptr.next = next_dataelif select == "2":  # 遍历查看链表所有节点ergodic(head, is_print=True)  # 遍历链表，将打印参数设为Trueelif select == '3':  # 向链表中任意位置插入节点，位置以序号表示，即第一个节点序号为1，第二个节点序号为2，以此类推try:num = int(input("请输入需要插入的节点位置序号："))  # 输入序号必须是大于0的正整数，如果输入大于最后一个节点的序号则插入到最后一个节点之后if num < 1:print("输入必须为大于0的正整数")continueexcept ValueError:print("输入有误")continueptr = ergodic(head, num-1)  # 获取需要插入位置的前一个节点insert_data = Player()insert_data.name = input("姓名：")insert_data.score = input("分数：")insert_data.next = ptr.nextptr.next = insert_dataif num == 1:  # 如果插入位置是1的话，那么head将发生变化head = insert_dataelif select == '4':  # 删除链表中任意位置的节点try:num = int(input("请输入需要删除的节点位置序号："))  # 输入序号必须是大于0的正整数，如果输入大于最后一个节点的序号则删除最后一个节点if num < 1:print("输入必须为大于0的正整数")continueexcept ValueError:print("输入有误")continueptr = ergodic(head, num - 1)  # 获取需要删除位置的前一个节点if ptr == ergodic(head, num):  # 输入序号过大时需要做特殊处理，因为输入序号过大也代表删除最后一个节点，那么这时我需要获取这最后一个节点的前一个节点ptr = ergodic(ptr)ptr.next = ptr.next.nextif num == 1:  # 如果删除位置是1的话，那么head将发生变化head = ptr.nextelif select == '5':  # 反转链表new_first = invert(head)  # 获取新的第一个节点head = new_first  # head指向新的第一个节点print('成功反转')elif select == '6':print("成功离开")breakelse:print("输入错误，请重试")

部分运行结果如下：