python链表反转讲解

Python链表反转的方法是什么

在编程中，链表是一种常见的数据结构，它由一系列的节点组成，每个节点包含两部分：数据和指向下一个节点的指针，链表的反转是将链表中的元素顺序颠倒过来，原链表为1->2->3->4，反转后的链表为4->3->2->1，接下来，我们将介绍如何在Python中实现链表的反转。

定义链表节点

我们需要定义一个链表节点类，该类包含两个属性：数据和指向下一个节点的指针。

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

反转链表

我们可以使用迭代或递归的方法来反转链表。

迭代方法

迭代方法是通过一个临时变量来保存当前节点，然后遍历链表，将当前节点的下一个节点设置为前一个节点，最后返回新的头节点。

def reverseList(head):
    prev = None
    current = head
    while current:
        next_temp = current.next
        current.next = prev
        prev = current
        current = next_temp
    return prev

递归方法

递归方法是通过递归调用自身来遍历链表，直到遍历到最后一个节点，然后将最后一个节点的next指向头节点，实现链表的反转。

def reverseList(head):
    if not head or not head.next:
        return head
    p = reverseList(head.next)
    head.next.next = head
    head.next = None
    return p

测试代码

我们可以编写一些测试代码来验证我们的解决方案。

def printList(node):
    while node:
        print(node.val, end=" ")
        node = node.next
    print()
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
print("原始链表：", end=" ")
printList(head)
head = reverseList(head)
print("反转后的链表：", end=" ")
printList(head)

运行上述测试代码，输出结果应为：原始链表： 1 2 3 4 和反转后的链表： 4 3 2 1 ，这说明我们的代码可以正确地反转链表。