LeetCode LCR 024. 反转链表

Categories:

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

题目描述

✅ LCR 024. 反转链表

思路分析

解法一：迭代（推荐）

核心思路：

用三个指针原地反转：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	中等	链表、指针操作
25. K 个一组翻转链表	困难	链表、递归
24. 两两交换链表中的节点	中等	链表、递归
234. 回文链表	简单	链表、快慢指针
143. 重排链表	中等	链表、反转
61. 旋转链表	中等	链表
2. 两数相加	中等	链表
445. 两数相加 II	中等	链表、反转
1721. 交换链表中的节点	中等	链表、双指针

本文作者: HGNULB

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