LeetCode反转链表：从迭代到递归，吃透链表操作的核心逻辑

admin 2026-02-09 阅读:13 评论:0

作为LeetCode第206题，LeetCode反转链表迭代与递归是链表操作的“入门级标杆题”——它不仅是大厂技术面试的高频考点（据鳄鱼java算法课2025年统计，95%的互联网大厂面试会涉及链表反转或其变体），更是理解“指针操作”与“递...

作为LeetCode第206题，LeetCode反转链表迭代与递归是链表操作的“入门级标杆题”——它不仅是大厂技术面试的高频考点（据鳄鱼java算法课2025年统计，95%的互联网大厂面试会涉及链表反转或其变体），更是理解“指针操作”与“递归思维”的核心载体。很多新手第一次接触链表时会被指针绕晕，但通过这道题能快速掌握链表反转的两种核心方法：迭代解法通过手动控制指针顺序实现反转，递归解法则利用递归栈回溯处理指针，两种方法分别对应“迭代思维”与“分治思维”，为后续解决K个一组反转链表、反转链表II等复杂问题打下基础。鳄鱼java学员数据显示，吃透这道题后，链表相关题的平均通过率从30%提升到92%，足见其作为“链表操作基石”的核心价值。

题解前置：反转链表的题意与核心边界用例

要掌握LeetCode反转链表迭代与递归，首先得明确核心要求：给你单链表的头节点head，反转链表，并返回反转后的新头节点。例如输入[1,2,3,4,5]，输出[5,4,3,2,1]；输入空链表，返回null；输入单节点[1]，返回[1]。

鳄鱼java算法课导师会反复强调：解题前必须覆盖三大边界用例，否则80%的提交会失败： 1. 空链表：输入null，返回null； 2. 单节点链表：输入[1]，返回[1]； 3. 双节点链表：输入[1,2]，返回[2,1]。

新手最容易犯的错误是忽略空链表和单节点情况，导致代码出现空指针异常或错误返回原节点，鳄鱼java学员提交数据显示，40%的第一次提交会因边界用例处理不当失败。

迭代解法：手动控制指针，避免断链的核心逻辑

迭代解法的核心是用三个指针维护当前节点、前一个节点和后一个节点，依次反转指针指向，避免链表断链。很多新手觉得迭代绕，本质是没理清指针的顺序：必须先保存当前节点的下一个节点，再反转当前节点的指针，否则会丢失后续节点的引用。

迭代解法的步骤拆解（鳄鱼java导师总结的“三步走”）： 1. 初始化指针：prev（前一个节点）设为null，curr（当前节点）设为head，next（下一个节点）暂存； 2. 循环反转指针：遍历链表时，先保存curr.next到next，再将curr.next指向prev，实现当前节点的反转； 3. 移动指针：prev移动到curr，curr移动到next，直到curr为null，此时prev就是反转后的新头节点。

Java迭代实现代码（带详细注释）：

 
public ListNode reverseList(ListNode head) { 
    // 初始化前一个节点为null，当前节点为头节点 
    ListNode prev = null; 
    ListNode curr = head; 
    while (curr != null) { 
        // 必须先保存当前节点的下一个节点，避免断链 
        ListNode nextTemp = curr.next; 
        // 反转当前节点的指针，指向前一个节点 
        curr.next = prev; 
        // 前一个节点后移到当前节点 
        prev = curr; 
        // 当前节点后移到下一个节点 
        curr = nextTemp; 
    } 
    // 循环结束时，prev是反转后的新头节点 
    return prev; 
}

鳄鱼java学员常踩的坑：先移动curr再保存nextTemp，导致curr.next已被覆盖，丢失后续节点；或者忘记将curr.next设为prev，直接移动指针，链表未反转。迭代解法的时间复杂度是O(n)，空间复杂度是O(1)，是面试中最被认可的“最优解”，因为空间效率更高。

递归解法：用递归栈回溯，理解“递”与“归”的过程

递归解法的核心是将大问题拆解为小问题：反转整个链表 = 反转当前节点 + 反转剩余链表，利用递归栈的回溯过程完成指针反转。很多新手觉得递归抽象，本质是没理清“递”和“归”的两个阶段： - 递的阶段：从head开始，不断调用递归函数，直到递归到链表的最后一个节点（终止条件：head==null或head.next==null，此时返回head作为新头节点）； - 归的阶段：回溯时，将当前节点的下一个节点的next指向当前节点，再将当前节点的next设为null，完成局部反转，最终返回新头节点。

Java递归实现代码（带注释）：

 
public ListNode reverseList(ListNode head) { 
    // 递归终止条件：空链表或单节点链表，直接返回head 
    if (head == null || head.next == null) { 
        return head; 
    } 
    // 递到最后一个节点，newHead是反转后的新头节点 
    ListNode newHead = reverseList(head.next); 
    // 归的阶段：反转当前节点和下一个节点的指针 
    head.next.next = head; 
    // 避免形成环，将当前节点的next设为null 
    head.next = null; 
    // 传递新头节点 
    return newHead; 
}

鳄鱼java导师会用动画演示递归栈的过程：比如链表[1,2,3,4,5]，递到节点5时返回，归到节点4时，将5的next指向4，4的next设为null；再归到节点3，将4的next指向3，3的next设为null，以此类推。递归解法的时间复杂度是O(n)，空间复杂度是O(n)（递归栈的深度等于链表长度），当链表长度超过1000时会出现栈溢出，这是迭代解法的优势。

迭代vs递归：面试中如何选择与回答

面试中，面试官常问“迭代和递归的区别是什么？哪种更优？”，鳄鱼java导师会指导学员从三个维度回答： 1. 空间复杂度：迭代是O(1)，递归是O(n)，迭代更省空间，适合处理长链表； 2. 代码简洁性：递归代码更简洁，逻辑更直观，适合快速实现； 3. 稳定性：迭代不会出现栈溢出，稳定性更高；递归在链表很长时会抛出StackOverflowError，稳定性不足。

面试技巧：先写迭代解法，说明其空间优势；再写递归解法，说明代码简洁性；当面试官追问“有没有更优解”时，强调迭代的O(1)空间是最优解，体现对时空复杂度的理解。鳄鱼java学员数据显示，面试中能同时写出两种解法并对比的，通过率比只写一种解法高60%。

鳄鱼java学员实战避坑指南：常见错误与解决方法

根据鳄鱼java学员的实战经验，两种解法的常见错误分别是： 1. 迭代解法错误：指针顺序错误，先移动curr再保存nextTemp，导致断链。解决方法：记住“先存next，再反转，后移动”的顺序； 2. 递归解法错误：忘记将当前节点的next设为null，导致链表形成环；或者递归终止条件错误，只判断head==null，漏掉head.next==null，导致空指针异常。解决方法：递归终止条件必须包含head.next==null，回溯时必须将head.next设为null； 3. 空链表处理错误：两种解法都未处理空链表，导致空指针异常。解决方法：在迭代前判断head==null直接返回null，递归终止条件包含head==null。