Python实现环形链表详解

共计 1474 个字符，预计需要花费 4 分钟才能阅读完成。

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

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

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

class Player:
    """节点类"""
    def __init__(self):
        """初始化姓名，分数，指针"""
        self.name = ''
        self.score = 0
        self.next = None
  
  
def ergodic(head, num=None, is_print=False):
    """遍历函数，num 是遍历到哪一个位置序号，is_print 是否触发打印方法"""
    if head.next is None:
        return None
    ptr = head
    count = 0
    while True:
        count += 1
        if is_print:
            print('No.'+str(count), ptr.name, ptr.score, '--->', ptr.next.name)
        if count == num:
            break
        if ptr.next == head:
            break
        ptr = ptr.next
    return ptr  # 返回遍历完成后的最后一个节点
  
  
def invert(x):  # x 是链表的第一个节点
    """反转环形链表"""
    y = x.next  # y 是 x 原来的 next
    x.next = ergodic(x)  # 将第一个节点的 next 指向最后一个节点 (因为反转了)
    while True:  # 循环反转后面的所有节点
        r = y.next
        y.next = x
        if r == head:  # r 是 head 说明 y 已经是原本链表的最后一个节点了
            return y  # 返回 y，这个 y 是反转后的链表的第一个节点
        x = y
        y = r
  
  
head = Player()
ptr = head
  
  
while True:
    select = input("(1). 新增   (2). 查看   (3). 插入   (4). 删除   (5). 反转   (6). 离开 \n 输入：")
    if select == "1":  # 新增节点
        ptr = ergodic(head)  # 获取当前链表最后一个节点
        if ptr is None:  # ptr 为 None 说明当前在添加第一个节点 head
            head.name = input("姓名：")
            head.score = input("分数：")
            head.next = head
        else:  # 添加第一个节点之后的节点
            next_data = Player()
            next_data.name = input("姓名：")
            next_data.score = input("分数：")
            next_data.next = head
            ptr.next = next_data
  
    elif select == "2":  # 遍历查看链表所有节点
        ergodic(head, is_print=True)  # 遍历链表，将打印参数设为 True
  
    elif select == '3':  # 向链表中任意位置插入节点，位置以序号表示，即第一个节点序号为 1，第二个节点序号为 2，以此类推
        try:
            num = int(input("请输入需要插入的节点位置序号："))  # 输入序号必须是大于 0 的正整数，如果输入大于最后一个节点的序号则插入到最后一个节点之后
            if num 
 部分运行结果如下：

 以上就是本文的全部内容，希望对大家的学习有所帮助。

 阿里云 2 核 2G 服务器 3M 带宽 61 元 1 年，有高配 
 腾讯云新客低至 82 元 / 年，老客户 99 元 / 年 
 代金券：在阿里云专用满减优惠券