基于Python实现2种反转链表方法代码实例

当我们需要对链表进行反转的时候，在Python中有很多种实现方式。本文将详细阐述两种反转链表的实现方法及其代码实例。

方法一：反转链表法

反转链表是最基础的一种方法，其实现思路很简单，就是对链表中的每个节点按照它们的next指针进行反转。首先我们定义一个新的链表头节点，然后遍历原始链表，每遍历到一个节点就将其作为头节点的下一节点，同时将其从原链表中删除。这样就能实现链表的反转。

代码实例：

class Node(object):
    def __init__(self, val):
        self.val = val
        self.next = None

class Solution(object):
    def reverseList(self, head):
        new_head = None
        while head:
            tmp = head.next
            head.next = new_head
            new_head = head
            head = tmp
        return new_head

以上代码中，我们首先定义了一个Node类来表示链表中的节点，每个节点都具有一个值val和一个next指针，指向链表中的下一节点。然后我们实现了一个Solution类，其中reverseList方法接收链表的头节点head作为参数，其返回值为反转后的链表的头节点new_head。

在while循环中，我们不断遍历原链表。定义临时变量tmp作为head节点的next指针，来记录下一个节点。然后将head节点指向new_head，将new_head更新为head节点，最后将head节点指向tmp节点。这样遍历结束后，new_head就成为了原链表的反转链表。

方法二：递归反转链表法

递归反转链表法是另一种实现反转链表的方法，它的实现思路是通过递归实现反转链表。具体实现追溯到链表的末尾，然后反向遍历链表，每次修改链表的next指针，进行链表反转。

代码实例：

class Solution(object):
    def reverseList(self, head):
        if not head or not head.next:
            return head
        new_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return new_head

以上代码中，我们还是定义了一个Solution类，其中reverseList方法的输入参数与方法一相同。当反转到最后一个节点时，我们返回该节点。然后，我们在反向遍历链表的过程中，每次都将当前节点的next指针指向前一个节点。这样反转完成时，我们返回的新的头节点就是原链表的尾节点。

示例：

我们通过一个示例来说明方法一的实现过程：

链表 1 -> 2 -> 3 -> 4 -> 5 -> null

开始时，新链表头节点new_head为null。

第一步：tmp = 2, head.next = null, new_head = 1, head = 2

新链表：2->1->null，原链表：3->4->5->null

第二步：tmp = 3, head.next = 2, new_head = 2, head = 3

新链表：3->2->1->null，原链表：4->5->null

以此类推，直到原链表遍历结束，新链表形成反转链表。

我们再通过一个示例来说明方法二的实现过程：

链表 1 -> 2 -> 3 -> 4 -> 5 -> null

开始时，递归反转链表，传入头节点1。

第一步：第一次递归，传入1->2->3->4->5->null

第二步：第二次递归，传入2->3->4->5->null

第三步：第三次递归，传入3->4->5->null

第四步：第四次递归，传入4->5->null

第五步：第五次递归，传入5->null

第六步：最后一次递归，传入null

回溯的过程中进行链表反转：

null<-5<-4<-3<-2<-1

递归结束后，我们的新链表头节点就为5。