Python OJ题典型：链表反转的迭代和递归

算法介绍

本文将介绍如何反转链表，即将原链表的头节点变为新链表的尾节点。我们将通过迭代和递归两种方式实现链表的反转。

算法解析

给定一个链表，我们需要实现一个函数来反转这个链表，并返回反转后的链表头节点。

解题思路

1. 迭代法

迭代法是最常见的解决链表反转的方法。我们可以使用三个指针，分别指向前一个节点、当前节点和下一个节点。通过不断更新指针的指向，将链表中的节点一个个反转。

具体步骤如下：

1. 初始化指针 prev 为 None，指针 curr 为链表的头节点。
2. 循环遍历链表，直到当前节点 curr 为空。
   1. 将当前节点的下一个节点保存为临时变量 next。
   2. 将当前节点的 next 指向前一个节点 prev。
   3. 更新指针 prev 为当前节点 curr。
   4. 更新指针 curr 为临时变量 next。
3. 循环结束后，返回更新后的链表头节点 prev。

2. 递归法

递归法是另一种实现链表反转的方法。递归的思想是将大问题分解为小问题的求解，直到达到基本情况。

具体步骤如下：

1. 定义递归函数 reverseList，接收一个链表节点作为参数。
2. 当前节点为空或者下一个节点为空时，直接返回当前节点。
3. 递归调用 reverseList 函数，传入下一个节点，并将返回结果保存为变量 newHead。
4. 将下一个节点的 next 指向当前节点。
5. 将当前节点的 next 设为 None。
6. 返回 newHead。

代码实现

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

def reverseListIteratively(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev

def reverseListRecursively(head):
    if not head or not head.next:
        return head

    new_head = reverseListRecursively(head.next)
    head.next.next = head
    head.next = None

    return new_head

# 测试示例
# 创建链表 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)

# 迭代法反转链表
iterative_result = reverseListIteratively(head)

# 递归法反转链表
recursive_result = reverseListRecursively(head)

解题技巧

• 迭代法适用于链表反转问题，使用三个指针进行节点更新。
• 递归法通过不断调用函数自身来解决链表反转问题，需要注意停止条件和指针的更新。

总结

本文介绍了两种方法来实现链表的反转：迭代法和递归法。迭代法通过使用三个指针来反转链表中的节点，而递归法则是通过不断调用函数自身来实现链表的反转。根据实际情况选择合适的方法来解决链表反转问题。