Python怎么實現單鏈表中元素的反轉

Python怎么實現單鏈表中元素的反轉

在數據結構中，單鏈表是一種常見的數據結構，它由一系列節點組成，每個節點包含數據和指向下一個節點的指針。單鏈表的反轉是一個經典的算法問題，通常用于面試和算法練習中。本文將介紹如何使用Python實現單鏈表中元素的反轉。

單鏈表的基本結構

首先，我們需要定義單鏈表的基本結構。一個單鏈表節點通常包含兩個部分：數據和指向下一個節點的指針。我們可以使用Python類來定義單鏈表節點：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

在這個類中，val表示節點的值，next是指向下一個節點的指針。

單鏈表的反轉算法

單鏈表的反轉算法有多種實現方式，本文將介紹兩種常見的方法：迭代法和遞歸法。

1. 迭代法

迭代法是一種直觀且易于理解的方法。它的基本思想是遍歷鏈表，逐個反轉節點的指針方向。具體步驟如下：

1. 初始化三個指針：prev、curr和next。prev指向當前節點的前一個節點，curr指向當前節點，next指向當前節點的下一個節點。
2. 遍歷鏈表，將curr.next指向prev，然后依次移動prev、curr和next指針。
3. 當curr為空時，鏈表反轉完成，prev即為新的頭節點。

以下是迭代法的Python實現：

def reverseList(head: ListNode) -> ListNode:
    prev = None
    curr = head
    
    while curr:
        next_node = curr.next  # 保存下一個節點
        curr.next = prev       # 反轉當前節點的指針
        prev = curr            # 移動prev指針
        curr = next_node       # 移動curr指針
    
    return prev  # 返回新的頭節點

2. 遞歸法

遞歸法是一種更為簡潔的實現方式，但理解起來可能稍微復雜一些。遞歸法的基本思想是：假設鏈表的其余部分已經被反轉，現在只需要反轉當前節點和剩余部分的關系。

具體步驟如下：

1. 遞歸調用反轉函數，直到到達鏈表的最后一個節點。
2. 在遞歸返回的過程中，將當前節點的next指針指向其前一個節點。
3. 最終返回新的頭節點。

以下是遞歸法的Python實現：

def reverseList(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    
    new_head = reverseList(head.next)  # 遞歸反轉剩余部分
    head.next.next = head              # 反轉當前節點和下一個節點的關系
    head.next = None                   # 斷開當前節點的next指針
    
    return new_head  # 返回新的頭節點

示例

假設我們有一個單鏈表 1 -> 2 -> 3 -> 4 -> 5，我們可以使用上述方法將其反轉為 5 -> 4 -> 3 -> 2 -> 1。

# 創建鏈表 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)

# 反轉鏈表
reversed_head = reverseList(head)

# 輸出反轉后的鏈表
while reversed_head:
    print(reversed_head.val, end=" -> ")
    reversed_head = reversed_head.next
# 輸出: 5 -> 4 -> 3 -> 2 -> 1 ->

總結

單鏈表的反轉是一個基礎但重要的算法問題。本文介紹了兩種常見的實現方法：迭代法和遞歸法。迭代法通過遍歷鏈表逐個反轉節點的指針方向，而遞歸法則通過遞歸調用反轉剩余部分并處理當前節點。兩種方法各有優缺點，選擇哪種方法取決于具體的應用場景和個人偏好。

通過掌握單鏈表的反轉算法，不僅可以加深對鏈表數據結構的理解，還能為更復雜的算法問題打下堅實的基礎。