反转链表的Python实现

反转链表是一种常见的链表操作，它可以将链表中的节点顺序反转。在Python中，我们可以使用迭代或递归的方式实现链表的反转。以下是反转链表的Python实现：

一、迭代实现

迭代实现是通过遍历链表将节点指针反转的方法。

# 定义链表节点类
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    prev = None
    curr = head
    while curr:
        temp = curr.next
        curr.next = prev
        prev = curr
        curr = temp
    return prev

# 创建链表
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
head.next = node2
node2.next = node3
node3.next = node4

# 反转链表
new_head = reverse_list(head)

# 输出反转后的链表
while new_head:
    print(new_head.val)
    new_head = new_head.next

以上代码中，我们使用两个指针prev和curr，将curr的next指针指向prev，从而实现链表的反转。在遍历过程中，我们需要一个临时变量temp来保存curr的下一个节点，以免丢失信息。

二、递归实现

递归实现是通过递归调用函数将当前节点后续的链表反转，并将当前节点的next指针指向前一个节点的方式实现。

def reverse_list_recursive(head):
    if not head or not head.next:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head
    head.next = None
    return new_head

# 创建链表
head = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
head.next = node2
node2.next = node3
node3.next = node4

# 反转链表
new_head = reverse_list_recursive(head)

# 输出反转后的链表
while new_head:
    print(new_head.val)
    new_head = new_head.next

以上代码中，我们通过递归调用函数实现链表的反转。在递归调用过程中，我们不断缩小问题规模，直到遇到最后一个节点或空节点为止，然后逐层返回反转后的链表的头节点。

三、小结

反转链表是一种常见的链表操作，可以通过迭代或递归的方式实现。在迭代实现中，我们使用两个指针来遍历链表并反转节点指针；在递归实现中，我们通过递归调用函数将当前节点后续的链表反转，并将当前节点的next指针指向前一个节点。以上是反转链表的Python实现示例。