链表简单2 种解法

#206反转链表

反转单链表的 next 方向并返回新的头节点。

#链表#递归

解题主线

迭代时必须先保存 next，再修改 current.next，否则会丢失未处理部分。

递归返回后让 head.next.next 指回 head，并把 head.next 置 null 断开旧方向。

解法 1：迭代反转

维护 previous、current 和 next，逐条把 next 边反向。

时间复杂度

O(n)

空间复杂度

O(1)

206. 反转链表 · 迭代反转

java

public class Solution {
    static final class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public ListNode reverseList(ListNode head) {
        ListNode previous = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        return previous;
    }
}

维护 previous、current 和 next，逐条把 next 边反向。

解法 2：递归反转

先反转 head.next 开始的后缀，回溯时把后继指回 head 并切断 head 的旧后继。

时间复杂度

O(n)

空间复杂度

O(n)（递归栈）

206. 反转链表 · 递归反转

java

public class Solution {
    static final class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

先反转 head.next 开始的后缀，回溯时把后继指回 head 并切断 head 的旧后继。

边界与易错点

递归版本若不执行 head.next = null，会在原头部附近形成环。
递归深度为 n，超长链表可能导致栈溢出，生产代码通常优先迭代。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

Q206_ReverseList.java