python单链表如何反转

发布时间：2022-05-07 12:08:28 作者：iii
来源：亿速云阅读：290

Python单链表如何反转

在数据结构中，单链表是一种常见的线性数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。单链表的反转是一个经典的算法问题，掌握它对于理解链表操作和递归思想非常有帮助。本文将详细介绍如何在Python中实现单链表的反转，并提供两种常见的实现方法：迭代法和递归法。

1. 单链表的基本结构

在开始反转单链表之前，我们首先需要定义单链表的基本结构。一个单链表节点通常包含两个部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。

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

在这个定义中，ListNode类表示单链表的一个节点。val是节点的数据，next是指向下一个节点的指针。

2. 迭代法反转单链表

迭代法是一种通过循环来逐步反转链表的方法。其基本思想是使用三个指针：prev、curr和next。prev指向当前节点的前一个节点，curr指向当前节点，next指向当前节点的下一个节点。通过不断更新这三个指针，我们可以逐步将链表反转。

2.1 实现步骤

初始化prev为None，curr为链表的头节点。
遍历链表，直到curr为None：
- 保存curr的下一个节点到next。
- 将curr的next指针指向prev。
- 将prev移动到curr。
- 将curr移动到next。
最后，prev将指向反转后的链表的头节点。

2.2 代码实现

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  # prev现在是新的头节点

2.3 示例

假设我们有一个单链表：1 -> 2 -> 3 -> 4 -> 5，使用迭代法反转后，链表将变为：5 -> 4 -> 3 -> 2 -> 1。

3. 递归法反转单链表

递归法是另一种反转单链表的方法。其基本思想是将链表分为头节点和剩余部分，递归地反转剩余部分，然后将头节点连接到反转后的剩余部分的末尾。

3.1 实现步骤

递归的终止条件是当前节点为空或当前节点的下一个节点为空。
递归调用反转剩余部分的链表。
将当前节点的下一个节点的next指针指向当前节点。
将当前节点的next指针指向None。
返回反转后的链表的头节点。

3.2 代码实现

def reverseListRecursive(head: ListNode) -> ListNode:
    # 递归终止条件
    if not head or not head.next:
        return head
    
    # 递归反转剩余部分
    new_head = reverseListRecursive(head.next)
    
    # 将当前节点的下一个节点的next指针指向当前节点
    head.next.next = head
    
    # 将当前节点的next指针指向None
    head.next = None
    
    return new_head

3.3 示例

同样以链表1 -> 2 -> 3 -> 4 -> 5为例，使用递归法反转后，链表将变为：5 -> 4 -> 3 -> 2 -> 1。

4. 两种方法的比较

迭代法：迭代法通过循环逐步反转链表，空间复杂度为O(1)，时间复杂度为O(n)。它不需要额外的栈空间，适合处理较长的链表。
递归法：递归法通过递归调用反转链表，空间复杂度为O(n)（由于递归调用栈），时间复杂度为O(n)。递归法代码简洁，但在处理非常长的链表时可能会导致栈溢出。

5. 总结

单链表的反转是一个基础但重要的算法问题。通过迭代法和递归法，我们可以有效地反转单链表。迭代法适合处理较长的链表，而递归法则代码简洁，但在处理非常长的链表时需要注意栈溢出的问题。掌握这两种方法，可以帮助我们更好地理解链表操作和递归思想。

在实际应用中，选择哪种方法取决于具体的需求和场景。希望本文的介绍能够帮助你更好地理解和掌握单链表的反转操作。