LeetCode 206. 反转链表

Categories:

Tags:

题目描述
思路分析
1. 解法一：迭代（推荐）
2. 解法二：递归
相似题目

题目描述

✅ 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

进阶：

链表可以选用迭代或递归方式完成反转，尝试用两种方法实现。

思路分析

解法一：迭代（推荐）

核心思路：

用三个指针原地反转：pre 指向已反转部分头，cur 为当前节点，next 暂存后继。

每次仅修改一条边：cur.next = pre，然后整体前移。

循环结束时 pre 即新头节点。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表节点数。

空间复杂度：O(1)，仅使用常数额外指针。

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            // 保存后继节点
            ListNode next = cur.next;
            // 反转当前指针
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

func reverseList(head *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	for cur != nil {
		// 保存后继节点
		next := cur.Next
		// 反转当前指针
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

解法二：递归

核心思路：

递归到链表尾节点，尾节点作为新头。

回溯时让后继节点指回当前节点，再断开当前节点的 next。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表节点数。

空间复杂度：O(n)，递归栈深度与链表长度相同。

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 递归反转子链表
        ListNode newHead = reverseList(head.next);
        // 让后继节点指回自己
        head.next.next = head;
        // 断开原正向边
        head.next = null;
        return newHead;
    }
}

func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	// 递归反转子链表
	newHead := reverseList(head.Next)
	// 让后继节点指回自己
	head.Next.Next = head
	// 断开原正向边
	head.Next = nil
	return newHead
}

相似题目

题目	难度	考察点
92. 反转链表 II	中等	链表、区间反转
156. 上下翻转二叉树	中等	树、递归
234. 回文链表	简单	链表、快慢指针
2074. 反转偶数长度组的节点	中等	链表分组反转
2130. 链表最大孪生和	中等	链表、快慢指针
2487. 从链表中移除节点	中等	链表、单调栈
2807. 在链表中插入最大公约数	中等	链表、数学
25. K 个一组翻转链表	困难	链表、分组反转
24. 两两交换链表中的节点	中等	链表、递归
143. 重排链表	中等	链表、反转

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/71018228