Python如何實現環形鏈表

這篇文章主要介紹“Python如何實現環形鏈表”，在日常操作中，相信很多人在Python如何實現環形鏈表問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”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 < 1:
                print("輸入必須為大于0的正整數")
                continue
        except ValueError:
            print("輸入有誤")
            continue
        ptr = ergodic(head, num-1)  # 獲取需要插入位置的前一個節點
        insert_data = Player()
        insert_data.name = input("姓名：")
        insert_data.score = input("分數：")
        insert_data.next = ptr.next
        ptr.next = insert_data
        if num == 1:  # 如果插入位置是1的話，那么head將發生變化
            head = insert_data
 
    elif select == '4':  # 刪除鏈表中任意位置的節點
        try:
            num = int(input("請輸入需要刪除的節點位置序號："))  # 輸入序號必須是大于0的正整數，如果輸入大于最后一個節點的序號則刪除最后一個節點
            if num < 1:
                print("輸入必須為大于0的正整數")
                continue
        except ValueError:
            print("輸入有誤")
            continue
        ptr = ergodic(head, num - 1)  # 獲取需要刪除位置的前一個節點
        if ptr == ergodic(head, num):  # 輸入序號過大時需要做特殊處理，因為輸入序號過大也代表刪除最后一個節點，那么這時我需要獲取這最后一個節點的前一個節點
            ptr = ergodic(ptr)
        ptr.next = ptr.next.next
        if num == 1:  # 如果刪除位置是1的話，那么head將發生變化
            head = ptr.next
 
    elif select == '5':  # 反轉鏈表
        new_first = invert(head)  # 獲取新的第一個節點
        head = new_first  # head指向新的第一個節點
        print('成功反轉')
 
    elif select == '6':
        print("成功離開")
        break
    else:
        print("輸入錯誤，請重試")

部分運行結果如下：

到此，關于“Python如何實現環形鏈表”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！