LeetCode-Hot100刷题反转链表迭代递归

2025-03-09 约 1611 字预计阅读 4 分钟

https://bing.ee123.net/img/rand?artid=146128402

LeetCode Hot100刷题——反转链表（迭代+递归）

206.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

反转链表通常有两种方法：迭代法和递归法。

迭代法（双指针）

假设原来的链表是1->2->3->4->5->null，反转后变成null<-1<-2<-3<-4<-5。那在迭代的时候，初始状态应该是prev=null，current=head。然后循环处理每个节点：

在循环中，首先保存当前节点的下一个节点nextTemp，然后把当前节点的next指向prev。接着prev移动到current的位置，current移动到nextTemp的位置。直到current为null，此时prev就是新的头节点。

实现代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode current = head;
        ListNode prev = null;
        while (current != null) {
            ListNode nextTemp = current.next; // 保存下一个节点
            current.next = prev; /// 反转指针
            prev = current; // 前移prev
            current = nextTemp; // 前移current
        }
        return prev; // prev即为新链表的头结点
    }
}

步骤解释：

初始化指针 ：使用两个指针 prev 和 current ，初始时 prev 为 null ， current 指向头节点 head 。
遍历链表 ：在 current 不为 null 时循环处理每个节点。
- 保存下一个节点 ：临时存储 current.next 到 nextTemp ，防止反转指针后丢失后续节点。
- 反转指针 ：将当前节点 current 的 next 指向 prev ，完成当前节点的反转。
- 移动指针 ：将 prev 移动到当前 current 的位置， current 移动到之前保存的 nextTemp 位置。
返回新头节点 ：当循环结束时， current 为 null ， prev 指向原链表的最后一个节点，即反转后的新头节点。

递归法

递归方法的步骤如下：

递归终止条件：当前节点为空或下一个子节点为空，返回当前节点
递归反转后续链表，得到反转后的头结点
将当前节点的下一个节点的next指向当前节点，形成反转
将当前节点的next设为null，断开原来的连接
返回反转后的头结点

实现代码

class Solution {
    public ListNode reverseList(ListNode head) {
        // 递归法
        // 递归终止条件，空链表或单链表无需反转
        if (head == null || head.next == null) {
            return head;
        }

        // 递归反转后续链表，得到新头结点
        ListNode newHead = reverseList(head.next);

        // 调整指针方向，将当前节点的下一个节点的next指向自己
        head.next.next = head;

        // 断开当前节点的原指向，防止循环
        head.next = null;

        // 返回新头结点
        return newHead;
    }
}

示例分析

1. 递归调用栈展开

递归从头部节点 1 开始，逐层深入，直到链表末尾的节点 5 。以下是调用栈的展开过程：

reverseList(1) → reverseList(2) → reverseList(3) → reverseList(4) → reverseList(5)

终止条件触发 ：当调用 reverseList(5) 时， 5.next == null ，直接返回 5 （此时 newHead = 5 ）。

2. 递归回溯与指针调整

递归开始逐层回溯，每层处理当前节点并调整指针方向：

层 4（ head = 4 ）

输入链表状态 ： 4 → 5
操作步骤 ：
1. 收到下层返回的 newHead = 5 。
2. 调整指针 ： 4.next.next = 4 → 5.next = 4 （形成 5 → 4 ）。
3. 断开原链 ： 4.next = null （防止 4 → 5 循环）。
输出链表状态 ： 5 → 4 → null
返回： newHead = 5

层 3（ head = 3 ）

输入链表状态 ： 3 → 4 → null （原链未修改时， 3.next 仍指向 4 ）。
操作步骤 ：
1. 收到下层返回的 newHead = 5 。
2. 调整指针 ： 3.next.next = 3 → 4.next = 3 （形成 5 → 4 → 3 ）。
3. 断开原链 ： 3.next = null 。
输出链表状态 ： 5 → 4 → 3 → null
返回： newHead = 5

层 2（ head = 2 ）

输入链表状态 ： 2 → 3 → null （原链未修改时， 2.next 指向 3 ）。
操作步骤 ：
1. 收到下层返回的 newHead = 5 。
2. 调整指针 ： 2.next.next = 2 → 3.next = 2 （形成 5 → 4 → 3 → 2 ）。
3. 断开原链 ： 2.next = null 。
输出链表状态 ： 5 → 4 → 3 → 2 → null
返回： newHead = 5

层 1（ head = 1 ）

输入链表状态 ： 1 → 2 → null （原链未修改时， 1.next 指向 2 ）。
操作步骤 ：
1. 收到下层返回的 newHead = 5 。
2. 调整指针 ： 1.next.next = 1 → 2.next = 1 （形成 5 → 4 → 3 → 2 → 1 ）。
3. 断开原链 ： 1.next = null 。
输出链表状态 ： 5 → 4 → 3 → 2 → 1 → null
返回： newHead = 5

总结

递归终止条件 ：处理到链表末尾时直接返回。
递归分解问题 ：假设后续链表已反转，只需调整当前节点和下一个节点的指针。
指针操作 ：通过 head.next.next = head 和 head.next = null 完成局部反转并断开原链。

目录

LeetCode-Hot100刷题反转链表迭代递归

LeetCode Hot100刷题——反转链表（迭代+递归）

206.反转链表

迭代法（双指针）

递归法