[[[toc]]]

链表

反转单链表（返回新链表）

思路：

迭代法：从头遍历，逐个改变指针方向
不使用额外空间，时间 O(n)

// 链表节点
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

public class Main {
    // 反转链表，返回新的头节点
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode nextTemp = curr.next; // 保存下一个节点
            curr.next = prev;              // 反转指针
            prev = curr;                   // 前驱后移
            curr = nextTemp;               // 当前节点后移
        }
        return prev; // prev 就是新头
    }

    // 打印链表
    public static void printList(ListNode head) {
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val + " ");
            curr = curr.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // 构建链表 1 -> 2 -> 3 -> 4 ->5
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);

        System.out.println("原链表：");
        printList(head);

        ListNode newHead = reverseList(head);
        
        System.out.println("反转后：");
        printList(newHead);
    }
}

反转链表这 4 行代码到底在干嘛？

先记住一句话： 反转链表，就是把每一个节点的箭头，从「向后指」改成「向前指」。

举个超级简单的小例子

原链表： 1 → 2 → 3 → null

我们要变成： null ← 1 ← 2 ← 3

4 行代码逐行动画讲解

变量含义：

prev：上一个节点（一开始是 null）
curr：当前正在处理的节点
nextTemp：临时保存下一个节点（怕弄丢）

while (curr != null) {             // 只要还有节点没处理，就继续
    ListNode nextTemp = curr.next; // 1. 先把【下一个节点】藏起来
    curr.next = prev;              // 2. 反转箭头：当前节点 → 指向前一个节点
    prev = curr;                   // 3. prev 往前走一步
    curr = nextTemp;               // 4. curr 走到刚才藏起来的下一个节点
}

动画开始（超级生动）

初始状态

prev = null
curr = 1 -> 2 -> 3 -> null

第一次循环（处理节点 1）

nextTemp = curr.next → 保存 2
curr.next = prev → 1 → null（箭头反转！）
prev = curr → prev 来到 1
curr = nextTemp → curr 来到 2

现在变成：

null <- 1    2 -> 3 -> null
        ↑    ↑
      prev  curr

第二次循环（处理节点 2）

nextTemp = curr.next → 保存 3
curr.next = prev → 2 → 1（箭头反转！）
prev = curr → prev 来到 2
curr = nextTemp → curr 来到 3

现在变成：

null <- 1 <- 2    3 -> null
             ↑    ↑
           prev  curr

第三次循环（处理节点 3）

nextTemp = curr.next → 保存 null
curr.next = prev → 3 → 2（箭头反转！）
prev = curr → prev 来到 3
curr = nextTemp → curr 变成 null

现在变成：

null <- 1 <- 2 <- 3
              ↑
            prev

循环结束！

curr 变成 null 了，退出循环。

prev 就是新的头节点！

最终链表： 3 → 2 → 1 → null