python递归&迭代方法实现链表反转

接下来我将详细讲解如何使用Python的递归和迭代方法实现链表的反转。

什么是链表反转

链表反转（reverse a linked list）指的是将链表中的所有节点的指针方向都倒转，即原来指向下一个节点的指针变为指向前一个节点，这样可以让链表的尾部变为头部，实现链表的逆序。

实现方法

链表反转可以使用递归和迭代两种方法进行实现。

递归方法

递归反转链表的思路是：

• 递归到链表的最后一个节点；
• 从最后一个节点开始，将每个节点的下一个节点的指针指向自己；
• 返回反转后的链表头节点。

用Python代码实现递归反转链表：

# 定义节点结构
class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# 递归反转链表
def reverseList(head):
    if not head or not head.next:
        return head
    newHead = reverseList(head.next)
    head.next.next = head
    head.next = None
    return newHead

使用以下代码进行测试：

# 构造链表
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

# 打印反转前的链表
p = node1
while p:
    print(p.val, end=" ")
    p = p.next
print()

# 反转链表
newHead = reverseList(node1)

# 打印反转后的链表
p = newHead
while p:
    print(p.val, end=" ")
    p = p.next
print()

输出结果如下：

1 2 3 4 5 
5 4 3 2 1 

迭代方法

迭代反转链表的思路是：

• 使用三个指针分别指向当前节点、前一个节点和后一个节点；
• 当前节点指向前一个节点，然后三个指针依次向后移动一个节点；
• 返回反转后的链表头节点。

用Python代码实现迭代反转链表：

# 迭代反转链表
def reverseList(head):
    if not head or not head.next:
        return head
    pre = None
    cur = head
    nxt = head.next
    while cur:
        cur.next = pre
        pre = cur
        cur = nxt
        nxt = nxt.next if nxt else None
    return pre

使用以下代码进行测试：

# 构造链表
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
node5 = Node(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5

# 打印反转前的链表
p = node1
while p:
    print(p.val, end=" ")
    p = p.next
print()

# 反转链表
newHead = reverseList(node1)

# 打印反转后的链表
p = newHead
while p:
    print(p.val, end=" ")
    p = p.next
print()

输出结果如下：

1 2 3 4 5 
5 4 3 2 1 

总结

递归和迭代是两种常见的解决链表反转问题的方法。对于链表较长的情况下，使用迭代方法需要额外的空间来保存三个指针，因此递归方法更节省空间。但是在Python中，递归深度有限制，因此对于较长的链表还是推荐使用迭代方法来实现反转。