Easy

题目描述

给你单链表的头节点 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

进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路

解题思路

反转链表是经典的链表操作题目，主要有两种实现方式：迭代法和递归法。

方法一：迭代法（推荐）

迭代法的核心思想是使用三个指针：prev（前一个节点）、curr（当前节点）、next（下一个节点）。

  1. 初始化 prev = null，curr = head
  2. 遍历链表，对于每个节点：
    • 保存下一个节点：next = curr.next
    • 反转当前连接：curr.next = prev
    • 移动指针：prev = curr, curr = next
  3. 最终 prev 就是新的头节点

这种方法直观易懂，空间复杂度为 O(1)。

方法二：递归法

递归法的思路是先递归到链表末尾，然后从后往前逐步反转。核心在于理解递归的返回值始终是新链表的头节点，而当前层需要处理的是当前节点与下一节点的反转。

递归法代码更简洁，但需要额外的函数调用栈空间。对于长链表可能存在栈溢出风险，因此推荐使用迭代法。

代码实现

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        
        while (curr != nullptr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
};

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        
        while curr:
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        
        return prev

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        return prev;
    }
}

var reverseList = function(head) {
    let prev = null;
    let curr = head;
    
    while (curr !== null) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    
    return prev;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
迭代法O(n)O(1)
递归法O(n)O(n)

其中 n 为链表节点数量。迭代法只使用常数额外空间，递归法需要 O(n) 的函数调用栈空间。

相关题目