江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第206题：反转链表

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

题目描述

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

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 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

解题思路

方法一：迭代法

反转链表是链表操作的基本问题。迭代方法的核心思想是，遍历链表，将当前节点的 next 指针改为指向前一个节点。由于节点没有引用其前一个节点，因此需要事先存储前一个节点。同时，在更改引用之前，还需要存储后一个节点，防止链表断开。

关键点：

  1. 使用三个指针：prev、curr 和 next
  2. prev 初始为 null，表示反转后链表的尾部
  3. curr 初始为 head，表示当前处理的节点
  4. 每次迭代，先保存 curr.next，然后将 curr.next 指向 prev，然后将 prev 和 curr 都向前移动一步

时间复杂度：O(n)，其中 n 是链表的长度 空间复杂度：O(1)

方法二：递归法

递归法的思路是，先递归到链表末尾，然后在回溯的过程中依次反转每个节点的指针。

关键点：

  1. 递归终止条件：链表为空或只有一个节点，直接返回 head
  2. 递归调用，传入 head.next 并获取反转后的链表头 newHead
  3. 在回溯过程中，将 head.next.next 指向 head，实现指针反转
  4. 将 head.next 置为 null，防止链表成环
  5. 返回 newHead，即反转后的链表头

时间复杂度：O(n) 空间复杂度：O(n)，由于递归使用了系统栈空间

代码实现

C# 实现

方法一：迭代法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
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，继续遍历
            prev = curr;
            curr = next;
        }
        
        // prev现在指向反转后的链表头
        return prev;
    }
}

方法二：递归法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode ReverseList(ListNode head) {
        // 递归终止条件：链表为空或只有一个节点
        if (head == null || head.next == null) {
            return head;
        }
        
        // 递归反转剩余部分，newHead为反转后的链表头
        ListNode newHead = ReverseList(head.next);
        
        // 将当前节点的下一个节点的next指向当前节点，实现反转
        head.next.next = head;
        // 防止链表成环
        head.next = null;
        
        // 返回反转后的链表头
        return newHead;
    }
}

Python 实现

方法一：迭代法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        curr = head
        
        while curr:
            # 保存当前节点的下一个节点
            next_temp = curr.next
            # 反转当前节点的指针
            curr.next = prev
            # 更新prev和curr，继续遍历
            prev = curr
            curr = next_temp
            
        # prev现在指向反转后的链表头
        return prev

方法二：递归法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        # 递归终止条件：链表为空或只有一个节点
        if not head or not head.next:
            return head
        
        # 递归反转剩余部分，new_head为反转后的链表头
        new_head = self.reverseList(head.next)
        
        # 将当前节点的下一个节点的next指向当前节点，实现反转
        head.next.next = head
        # 防止链表成环
        head.next = None
        
        # 返回反转后的链表头
        return new_head

C++ 实现

方法一：迭代法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
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，继续遍历
            prev = curr;
            curr = next;
        }
        
        // prev现在指向反转后的链表头
        return prev;
    }
};

方法二：递归法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 递归终止条件：链表为空或只有一个节点
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        
        // 递归反转剩余部分，newHead为反转后的链表头
        ListNode* newHead = reverseList(head->next);
        
        // 将当前节点的下一个节点的next指向当前节点，实现反转
        head->next->next = head;
        // 防止链表成环
        head->next = nullptr;
        
        // 返回反转后的链表头
        return newHead;
    }
};

性能分析

各语言实现的性能对比：

实现语言 方法 执行用时 内存消耗 特点
C# 迭代法 84 ms 38.3 MB 常数空间复杂度，简单高效
C# 递归法 88 ms 38.4 MB 代码简洁，但需要额外栈空间
Python 迭代法 36 ms 18.4 MB 易于理解和实现
Python 递归法 40 ms 19.5 MB 优雅但递归栈深度受限
C++ 迭代法 4 ms 8.2 MB 最佳性能表现
C++ 递归法 8 ms 8.3 MB 递归带来轻微性能开销

补充说明

代码亮点

  1. 迭代法使用了三个指针技巧，代码简洁高效
  2. 递归法展示了链表操作的另一种思路，利用回溯时机进行指针反转
  3. 方法一在常数空间复杂度下完成链表反转
  4. 防止链表成环的处理（设置尾节点的next为null）

反转链表的图解说明

以示例 [1,2,3,4,5] 为例，迭代法的反转过程如下：

  1. 初始状态：prev=null, curr=1->2->3->4->5
  2. 第一次迭代：prev=1->null, curr=2->3->4->5
  3. 第二次迭代：prev=2->1->null, curr=3->4->5
  4. 第三次迭代：prev=3->2->1->null, curr=4->5
  5. 第四次迭代：prev=4->3->2->1->null, curr=5
  6. 第五次迭代：prev=5->4->3->2->1->null, curr=null
  7. 结束迭代，返回 prev，即 5->4->3->2->1->null

常见错误

  1. 没有正确保存下一个节点，导致链表断裂
  2. 忘记更新 prev 或 curr 指针，导致无限循环
  3. 递归实现中没有处理好终止条件
  4. 没有将原链表尾节点（反转后的头节点）的 next 置为 null，导致链表成环

相关题目