vvrf / DSA.log

问题拆解

要把 1 -> 2 -> 3 -> 4 -> 5 变成 5 -> 4 -> 3 -> 2 -> 1。链表不像数组能随机访问，只能顺着 next 一步步走，所以反转的动作只能落在“改写每个节点的 next 指向”上。

问题在于：当我们把 cur.next 从指向后继改成指向前驱时，原来的后继就找不到了。所以真正的关键是在改指针之前，先用一个变量把后继存下来。

反转链表不需要额外的容器，需要的是三个指针：已经反转好的前半段、当前节点、还没处理的后继。

迭代：三指针

public ListNode reverseList(ListNode head) {
    ListNode prev = null;
    ListNode cur = head;
    while (cur != null) {
        ListNode nxt = cur.next;
        cur.next = prev;
        prev = cur;
        cur = nxt;
    }
    return prev;
}

def reverseList(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev = cur
        cur = nxt
    return prev

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    cur := head
    for cur != nil {
        nxt := cur.Next
        cur.Next = prev
        prev = cur
        cur = nxt
    }
    return prev
}

pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    let mut prev = None;
    let mut cur = head;
    while let Some(mut node) = cur {
        cur = node.next.take(); // 先保住后继
        node.next = prev;       // 再掉头
        prev = Some(node);
    }
    prev
}

prev 是已经反转好的部分的头，初始为 None（反转后原来的头会变成尾，尾的 next 正是 None）。每一轮先存后继，再让当前节点掉头指向 prev，然后两个指针一起前移。循环结束时 cur 走到空，prev 恰好停在原链表的最后一个节点，也就是新的头。

递归

题目进阶希望两种写法都掌握。递归的思路是：先反转从 head.next 开始的子链表，拿回它的新头，再把 head 接到子链表的末尾。

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;
}

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

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return newHead
}

// Box 的独占所有权不允许“后继反过来指向自己”这种临时双向引用，
// 所以 Rust 的递归版换一种等价拆法：每层摘下头节点，接到已反转部分的前面。
pub fn reverse_list(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    fn helper(cur: Option<Box<ListNode>>, prev: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match cur {
            None => prev,
            Some(mut node) => {
                let rest = node.next.take();
                node.next = prev;
                helper(rest, Some(node))
            }
        }
    }
    helper(head, None)
}

关键的两行是 head.next.next = head（让后继反过来指向自己）和 head.next = None（断开原来的正向指针，否则会形成环）。new_head 在整条递归里一路向上原样返回，始终是原链表的尾节点。

复杂度

指标	复杂度	原因
时间	`O(n)`	每个节点只访问一次
空间	`O(1)` / `O(n)`	迭代只用常数指针；递归的栈深度是链表长度

可以迁移的模式

需要原地改写指针时，先用临时变量保住后继，再动手；
prev / cur / nxt 三指针是链表操作的基本手型；
递归写法把“反转整条”拆成“反转子链表 + 接回当前节点”。

一旦习惯了“存后继—改指针—前移”这套动作，后面很多链表题都是它的变体。