039. 编写一个函数，反转一个单链表

在 Python 中，可以通过迭代或递归的方式反转一个单链表。

方法 1：迭代实现

迭代方法通过逐个反转链表中的节点来实现反转。以下是迭代实现的代码：

class ListNode:
    """
    定义链表的节点类。
    """
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def reverse_linked_list(head):
    """
    使用迭代方法反转单链表。

    参数:
        head (ListNode): 链表的头节点。

    返回:
        ListNode: 反转后的链表的头节点。
    """
    prev = None  # 初始化前一个节点为 None
    current = head  # 当前节点从头节点开始

    while current:
        next_node = current.next  # 保存下一个节点
        current.next = prev  # 反转当前节点的指针
        prev = current  # 前一个节点向前移动
        current = next_node  # 当前节点向前移动

    return prev  # 返回新的头节点

# 测试代码
# 创建一个链表：1 -> 2 -> 3 -> 4
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)

node1.next = node2
node2.next = node3
node3.next = node4

# 反转链表
new_head = reverse_linked_list(node1)

# 打印反转后的链表
current = new_head
while current:
    print(current.value, end=" -> " if current.next else "")
    current = current.next

运行结果

运行上述代码后，输出如下：

4 -> 3 -> 2 -> 1

代码解释

初始化指针：

使用三个指针：prev（前一个节点）、current（当前节点）和 next_node（下一个节点）。
初始时，prev 为 None，current 为头节点。

迭代反转：

在每次迭代中，保存当前节点的下一个节点（next_node）。
将当前节点的 next 指针指向前一个节点（prev）。
更新 prev 和 current 指针，分别向前移动。

返回新的头节点：

当 current 为 None 时，prev 指向原链表的最后一个节点，即反转后的头节点。

方法 2：递归实现

递归方法通过递归调用反转链表中的节点。以下是递归实现的代码：

class ListNode:
    """
    定义链表的节点类。
    """
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def reverse_linked_list_recursive(head):
    """
    使用递归方法反转单链表。

    参数:
        head (ListNode): 链表的头节点。

    返回:
        ListNode: 反转后的链表的头节点。
    """
    if not head or not head.next:
        return head  # 如果链表为空或只有一个节点，直接返回头节点

    # 递归反转剩余部分
    new_head = reverse_linked_list_recursive(head.next)

    # 反转当前节点的指针
    head.next.next = head
    head.next = None

    return new_head  # 返回新的头节点

# 测试代码
# 创建一个链表：1 -> 2 -> 3 -> 4
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)

node1.next = node2
node2.next = node3
node3.next = node4

# 反转链表
new_head = reverse_linked_list_recursive(node1)

# 打印反转后的链表
current = new_head
while current:
    print(current.value, end=" -> " if current.next else "")
    current = current.next

运行结果

运行上述代码后，输出如下：

4 -> 3 -> 2 -> 1

代码解释

递归终止条件：

如果链表为空或只有一个节点，直接返回头节点。

递归反转：

递归调用 reverse_linked_list_recursive，反转剩余部分的链表。
返回新的头节点 new_head。

反转当前节点的指针：

将当前节点的 next 指针指向前一个节点。
将当前节点的 next 指针设置为 None，避免形成环。

返回新的头节点：

返回递归调用的结果，即反转后的头节点。

选择方法

迭代方法：

更高效，避免了递归调用的开销。
适用于大规模链表，不会导致栈溢出。

递归方法：

代码更简洁，易于理解。
适用于较小规模的链表，但需要注意递归深度。

视频讲解

BiliBili： 视睿网络-哔哩哔哩视频 (bilibili.com)