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 ->

总结

单链表的反转是一个基础但重要的算法问题。本文介绍了两种常见的实现方法：迭代法和递归法。迭代法通过遍历链表逐个反转节点的指针方向，而递归法则通过递归调用反转剩余部分并处理当前节点。两种方法各有优缺点，选择哪种方法取决于具体的应用场景和个人偏好。

通过掌握单链表的反转算法，不仅可以加深对链表数据结构的理解，还能为更复杂的算法问题打下坚实的基础。