单向链表逆转算法

单向链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个元素和一个指向下一个节点的引用。与数组不同的是，链表上的元素顺序存储在内存中，并且可以动态调整。单向链表的逆转是常见的操作之一，在算法设计和实现中具有重要意义。

单向链表的基本概念

在探讨单向链表逆转之前，先简要介绍一下单向链表的基本结构。一个典型的节点定义如下：

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

其中 val 是当前节点存储的值，next 指针指向下一个节点。

单向链表逆转算法

单向链表逆转的目标是将链表中的所有节点重新排序，使得原先为头结点的节点变为尾结点，而原来的尾结点成为新的头结点。实现这一目标的方法主要有两种：递归法和迭代法。

1. 迭代法

通过遍历单向链表并调整每个节点的 next 指针来完成逆转操作。具体步骤如下：

• 初始化三个指针 prev, curr, 和 next，分别指向当前节点的前驱、当前节点和后继。
• 将 head.next 设为 None 以断开旧链表与新链表之间的连接。
• 遍历整个链表，每次操作中：
  • 保存当前节点的下一个节点到变量 next 中。
  • 当前节点的 next 指向 prev（即设置逆转关系）。
  • 更新 prev 和 curr 的指向，移动至下一节点。

以下是迭代法的伪代码实现：

def reverseList(head):
    prev = None
    curr = head
    while curr is not None:
        next_node = curr.next  # 记录当前节点的下一个节点
        curr.next = prev       # 将当前节点指向 `prev`
        prev = curr            # 移动前驱指针
        curr = next_node       # 移动当前指针至下一节点
    return prev               # 返回新的头结点

2. 递归法

递归方法的实现相对简洁，但需要理解其工作原理。递归逆转链表的过程可以通过如下步骤来简化：

• 如果当前节点为空或只有一个节点，则直接返回该节点。
• 调用自身函数对剩余部分进行逆转。
• 更新原链表中第一个节点的 next 指针，使其指向当前第一个节点。

以下是递归法的伪代码实现：

def reverseList(head):
    if head is None or head.next is None:
        return head
    new_head = reverseList(head.next)
    head.next.next = head  # 设置逆转关系
    head.next = None       # 断开与后续节点的连接
    return new_head

总结

单向链表的逆转是数据结构中一个经典而又重要的操作。通过迭代法或递归法可以轻松实现这一目标，具体选择哪种方法主要取决于实际应用场景及个人偏好。无论是递归还是迭代，在实践中都能有效应对各种链表逆转的需求。