😀前言
在算法面试中，链表问题是一个常见的考点，而反转链表更是其中的经典题目之一。本篇文章将通过具体的代码实现和思路解析，带你深入理解反转链表的解法。

😀反转链表

NowCoder

😊问题描述

给定一个单链表的头结点 pHead，其长度为 n，要求将链表反转并返回反转后的新链表的头节点。我们需要在空间复杂度为 O(1) 和时间复杂度为 O(n) 的条件下完成这一操作。

例如，当输入链表为 {1,2,3} 时，经过反转后得到的链表应为 {3,2,1}。

以上转换过程如下图所示：

示例1

• 输入：{1,2,3}
• 输出：{3,2,1}

示例2

• 输入：{}
• 输出：{}
• 说明：空链表则输出为空。

😉解题思路

反转链表主要有两种解法：递归和迭代。下面我们将分别介绍这两种方法。

🥰递归解法

递归是一种非常自然的思维方式。在反转链表的问题中，递归的核心思想是将链表逐步缩短，并将缩短后的链表进行反转。具体来说，假设我们已经成功反转了链表的后半部分，那么我们只需要将当前节点接到反转后的链表末尾即可。

递归解法的代码实现如下：

public ListNode ReverseList(ListNode head) {
    // 基本情况：如果链表为空或只有一个节点，则直接返回当前节点
    if (head == null || head.next == null)
        return head;
    
    // 递归反转后续节点
    ListNode next = head.next;
    head.next = null;
    ListNode newHead = ReverseList(next);
    
    // 将当前节点接到反转后的链表末尾
    next.next = head;
    
    return newHead;
}

递归解法的分析

• 时间复杂度：O(n)。递归遍历了链表中的每一个节点，时间复杂度为 O(n)。
• 空间复杂度：O(n)。由于递归函数调用占用了系统栈空间，空间复杂度为 O(n)，不满足题目对 O(1) 空间复杂度的要求。

虽然递归解法简单直观，但由于其空间复杂度为 O(n)，不满足题目的要求。因此，在实际应用中，我们通常选择迭代解法。

🥰迭代解法

迭代解法通过头插法实现链表的反转。在遍历链表的过程中，将当前节点插入到新链表的头部，从而完成链表的反转。

迭代解法的代码实现如下：

public ListNode ReverseList(ListNode head) {
    // 创建一个新的空链表，用于存储反转后的节点
    ListNode newList = new ListNode(-1);
    
    while (head != null) {
        // 保存当前节点的下一个节点
        ListNode next = head.next;
        
        // 将当前节点插入到新链表的头部
        head.next = newList.next;
        newList.next = head;
        
        // 移动到下一个节点
        head = next;
    }
    
    // 返回新链表的头节点
    return newList.next;
}

迭代解法的分析

• 时间复杂度：O(n)。迭代遍历了链表中的每一个节点，时间复杂度为 O(n)。
• 空间复杂度：O(1)。由于我们只使用了常量级别的额外空间，空间复杂度为 O(1)。

迭代解法不仅满足题目对时间复杂度和空间复杂度的要求，还避免了递归深度过大的问题，是一种更为高效和实用的解决方案。

😄总结

反转链表问题是链表类题目中的经典问题，通过递归和迭代两种不同的方法，我们可以灵活应对各种场景。递归解法简单直观，但在空间复杂度上有所欠缺；而迭代解法则在时间和空间效率上更胜一筹，适合在实际工程中使用。

通过本文的学习，相信你已经掌握了反转链表的核心思路和两种主要解法。无论是在面试中还是实际开发中，希望这些技巧都能助你一臂之力。