Python实现链表反转的方法分析

链表是一种数据结构，它由一系列节点构成，每个节点包含一个值和指向下一个节点的指针。如果想要对链表进行操作，例如删除、插入或者反转等等，那么就需要了解如何正确地遍历链表。

本文将详细介绍Python实现链表反转的两种方法：迭代法和递归法，内容包括基础原理、代码实现以及示例说明。

基础原理

链表反转是指将链表中元素的前后顺序颠倒。在链表中，每个节点都包含一个指针，指向下一个节点。链表的头是指向第一个节点的指针。如果想要将链表反转，就需要改变每个节点中指针的指向，让其指向前一个节点。

迭代法实现链表反转

迭代法是通过遍历链表来实现链表反转的方法。具体的实现步骤如下：

初始化三个指针: prev, current 和 next，分别指向空节点(None), 链表的头节点和当前节点的下一个节点。
循环遍历当前链表，判断当前节点是否为空(None):

2.1. 保存当前节点的下一个节点(nxt)，以便在重置当前节点指针时能够继续遍历。

2.2. 将当前节点指向前一个节点(prev)。

2.3. 更新prev和current指针，以便继续遍历。

2.4. 将nxt指针赋值给current，以便继续遍历下一个节点。
当遍历完整个链表后，更新链表的头节点，并将它指向prev节点。

以下是Python代码示例：

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

def reverse_linked_list(head: ListNode) -> ListNode:
    prev, current, nxt = None, head, None
    while current:
        nxt = current.next
        current.next = prev
        prev = current
        current = nxt
    head = prev
    return head

递归法实现链表反转

除了迭代法之外，还可以使用递归法实现链表反转。具体实现步骤如下：

首先，判断链表是否为空，或是否只有一个节点。如果是，直接返回该链表。
递归反转链表。
对于当前节点的处理：将当前节点的下一个节点的next指针指向当前节点，然后将当前节点的next指针置为空。
返回反转后的列表头。

以下是Python代码示例：

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

def reverse_linked_list(head: ListNode) -> ListNode:
    if not head or not head.next:
        return head
    p = reverse_linked_list(head.next)
    head.next.next = head
    head.next = None
    return p

示例说明

为了更好地理解链表反转的过程，我们以一个简单的链表为例: 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)

调用函数reverse_linked_list()来反转链表：

head = reverse_linked_list(head)

输出反转后链表的结果：

print(head.val)
print(head.next.val)
print(head.next.next.val)
print(head.next.next.next.val)
print(head.next.next.next.next.val)
# Output: 5 4 3 2 1

示例二：使用递归法反转链表