反转链表

Source: Dev.to

目标

• 原地 反转单向链表。
• 最后一个节点变成第一个节点。
• 所有 next 指针都被反转。
• 返回反转后链表的新头节点。

直觉

单向链表节点保存一个值和指向下一个节点的引用。
如果在遍历链表的过程中，将每个节点的 next 指针重新指向它的前驱节点，链表就会被反转。

方法

在遍历链表时使用两个指针：

每次迭代时：

1. 将 curr.next 保存到临时变量（nextTemp）中。
2. 设置 curr.next = prev。
3. 将 prev 前移到 curr。
4. 将 curr 前移到 nextTemp。

当 curr 变为 null 时，prev 指向新的头节点。

算法（Java）

/**
 * Reverses a singly linked list in‑place.
 *
 * @param head the original head of the list
 * @return the new head after reversal
 */
Node reverseLL(Node head) {
    Node prev = null;      // will become the new head
    Node curr = head;      // current node being processed

    while (curr != null) {
        Node nextTemp = curr.next; // store next node
        curr.next = prev;          // reverse the link
        prev = curr;               // advance prev
        curr = nextTemp;           // advance curr
    }
    // prev is the new head
    return prev;
}

注意： Node 被假设为至少包含 Node next 字段的类。

示例演示

考虑链表 10 → 20 → 30 → 40 → null。

循环结束后，prev 指向 40，得到反转后的链表：

40 → 30 → 20 → 10 → null

边界情况

• 空链表： head == null → 函数返回 null。
• 单节点链表： head.next == null → 函数返回同一个节点（无需更改）。

最终输出

函数返回反转后链表的头节点，例如上述示例的结果为 40。