链表刷题——反转链表

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。 力扣地址： https://leetcode.cn/problems/reverse-linked-list/description/

迭代法

思路就是： 用 cur 遍历链表，逐个节点“掉头”指向 pre，最终 pre 成为新链表的头。 先说一下我们的目标就是：把所有箭头翻转

原链表：1 → 2 → 3 → … → null 期望变成：… ← 3 ← 2 ← 1，并返回新的头（原来的尾） 三根指针各干啥

• cur：手术台上的当前节点（还没被翻转的“未处理区”的第一个）
• pre：已翻转好的一段的“新头”
• next：缓存当前节点原本的下一个，防止“断链后找不到剩下的表” 这个next 的作用就是防止找不到到剩下的链表
• 初始化：pre = null（因为新链表的尾部应该指向 null）、cur = head

过程就是： 从 head 开始，用 cur 指针依次走过原链表的每一个节点，把它的 next 指针掉个头，改成指向前一个节点（pre）。

class Solution {
    public ListNode reverseList(ListNode head) {
        //检测是不是空链表
        if(head == null) {
            return null;
        }
//检测是不是只有一个元素
    if(head != null) {
        return head;
    }
      ListNode cur = head;
        ListNode pre = new ListNode();
       while (cur != null) {
            ListNode next = cur.next; // 先存下一个
            cur.next = prev;          // 反转指向
            prev = cur;               // 前移 prev
            cur  = next;              // 前移 cur
        }
      
    }
    return pre;
}

递归法

在链表里，递归通常有两个关键点：

• 基础条件：当链表是空 (head == null) 或只有一个节点 (head.next == null) 时，直接返回，不需要反转。
• 递归分解：把“大问题”拆成“反转剩下的子链表 + 处理当前节点”。 目标：反转 1 → 2 → 3 → null 递归的想法： 如果我能反转好 2 → 3 → null，得到 3 → 2 → null， 那么只需要把 1 接到 2 的后面，就完成整个链表的反转。

通俗讲：递归法就是 先把子链表反转好，再让当前节点挂到子链表尾巴后面，层层回溯，完成整个链表反转。

思路讲解：

每一层的过程（例子：1 → 2 → 3）：从最后一个节点开始转换方向，把链表的方向一层层“倒回来”

1. 递归到 3，返回 3。
2. 在 2 这层： newHead = 3 3.next = 2 2.next = null → 得到：3 → 2 → null → 返回 newHead = 3
3. 在 1 这层： newHead = 3 2.next = 1 1.next = null → 得到：3 → 2 → 1 → null → 返回 3

最终 newHead = 3，就是新的头。

执行过程（例子：1 → 2 → 3）

• Step 1: 调用 reverseList(1) 不满足基础条件 → 去调用 reverseList(2)
• Step 2: 调用 reverseList(2) 不满足基础条件 → 去调用 reverseList(3)
• Step 3: 调用 reverseList(3) 满足 head.next == null → 返回 3
• Step 4: 回溯到 2 newHead = 3 2.next.next = 2 → 让 3 → 2 2.next = null → 防止 2 → 3 → 2 形成环 返回 newHead = 3
• Step 5: 回溯到 1 newHead = 3 1.next.next = 1 → 让 2 → 1 1.next = null 返回 newHead = 3

最终结果：3 → 2 → 1 → null

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) {
            return head;
        }
        if( head.next == null) {
            return head;
        } 
      ListNode newHead = reverseList(head.next);
    head.next.next = head;
    //newHead.next = head;
    //把当前节点 head 接到它后一个节点（head.next）的后面，实现“反转指针方向”。
      head.next = null;      // 避免形成环
return newHead;
    }
}

头插法：

思想：

新建一个虚拟头 dummy；

每次把原链表的当前节点摘下来，插到 dummy 的后面；

最后 dummy.next 就是反转后的链表。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = null;
        while (head != null) {
            ListNode next = head.next; // 取下一个
            head.next = dummy;         // 插到前面
            dummy = head;              // 更新新链表头
            head = next;               // 原链表继续
        }
        //head为空，所以dummy   返回是为最后的结果
        return dummy;
    }
}

与前文差不多只是叫法不一样思路是一样的，这个比较好理解，就不多说了