在 Python 中反轉連結串列

連結串列是電腦科學中的一種線性資料結構，它提供恆定時間的元素新增和刪除。它由節點組成。

單個節點儲存一些資料和下一個節點的地址。下一個節點儲存它的資料和下一個節點的地址。單個節點只知道它指向的節點。它沒有關於指向它的節點的資訊。

這種結構允許我們在恆定時間內新增新節點和刪除現有節點，給定它之前的節點，這與陣列不同，我們必須將陣列複製到新陣列或移動陣列的元素以建立新增和刪除空間.

在陣列中，可以藉助索引在恆定時間內訪問元素。但是對於連結串列，訪問一個元素需要 O(n) 時間，其中 n 是連結串列的長度。

由於連結串列在結構上（線性）類似於陣列，因此我們還可以對連結串列進行排序、過濾和搜尋等操作。我們可以使用排序和搜尋演算法，例如氣泡排序、插入排序、歸併排序、快速排序、選擇排序、二分搜尋和連結串列上的線性搜尋。

本文將展示如何使用 Python 反轉連結串列。請注意，程式碼片段考慮了一個代表連結串列塊的 Node 類。

Node 類應如下所示。

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

在 Python 中反轉連結串列

參考以下 Python 程式碼在 Python 中反轉連結串列。

def reverse(head : Node) -> Node:
    previous = None
    current = head
    next = None
    
    while (current is not None):
        next = current.next
        current.next = previous
        previous = current
        current = next
    
    head = previous
    return head

要理解程式碼，請考慮一個示例連結串列，1 -> 2 -> 3 -> 4 -> 5 -> None。

首先，我們宣告三個變數 previous、current 和 next，它們分別指向輸入連結串列的頭部 None 和 None。接下來，我們宣告一個 while 迴圈，當 current 節點指向 None 時結束。

對於每次迭代：

• 我們將當前節點的下一個節點儲存在下一個節點中。
• 將 current 節點的下一個節點設定為 previous 節點。
• 將 previous 節點重置為 current 節點。
• 將 current 節點重置為 next 節點。

下表表示當演算法應用於上述示例時變數的值，即 previous、current 和 next 如何變化。

上面的表格單元格顯示了節點儲存的值。