LeetCode 92. 反转链表 II

Categories:

Tags:

题目描述
思路分析
1. 解法一：迭代（头插法）（推荐）
2. 解法二：递归（反转前 N 个节点）
相似题目

题目描述

✅ 92. 反转链表 II

思路分析

解法一：迭代（头插法）（推荐）

核心思路：

使用虚拟头节点 dummy 统一处理边界。

pre 指向待反转区间的前一个节点，cur 指向区间第一个节点。

每次把 cur.next 插到 pre 后面，实现局部头插。

复杂度分析：

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

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

// 头插法局部反转
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode pre = dummy;
        for (int i = 1; i < left; i++) {
            pre = pre.next;
        }

        ListNode cur = pre.next;
        for (int i = 0; i < right - left; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = pre.next;
            pre.next = next;
        }

        return dummy.next;
    }
}

// 头插法局部反转
func reverseBetween(head *ListNode, left int, right int) *ListNode {
	dummy := &ListNode{Next: head}
	pre := dummy

	for i := 1; i < left; i++ {
		pre = pre.Next
	}

	cur := pre.Next
	for i := 0; i < right-left; i++ {
		next := cur.Next
		cur.Next = next.Next
		next.Next = pre.Next
		pre.Next = next
	}

	return dummy.Next
}

解法二：递归（反转前 N 个节点）

核心思路：

若 left == 1，问题转化为反转链表前 right 个节点。

递归反转前 N 个节点，并记录后继节点 successor 用于接回。

复杂度分析：

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

空间复杂度：O(n)，递归栈深度最坏为 n。

// 递归反转前 N 个节点
class Solution {
    private ListNode successor;

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == 1) {
            return reverseN(head, right);
        }
        head.next = reverseBetween(head.next, left - 1, right - 1);
        return head;
    }

    private ListNode reverseN(ListNode head, int n) {
        if (n == 1) {
            successor = head.next;
            return head;
        }
        ListNode newHead = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = successor;
        return newHead;
    }
}

// 递归反转前 N 个节点
var successor *ListNode

func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if left == 1 {
		return reverseN(head, right)
	}
	head.Next = reverseBetween(head.Next, left-1, right-1)
	return head
}

func reverseN(head *ListNode, n int) *ListNode {
	if n == 1 {
		successor = head.Next
		return head
	}
	newHead := reverseN(head.Next, n-1)
	head.Next.Next = head
	head.Next = successor
	return newHead
}

相似题目

题目	难度	考察点
206. 反转链表	简单	链表反转基础
25. K 个一组翻转链表	困难	链表分组反转
24. 两两交换链表中的节点	中等	链表操作
234. 回文链表	简单	快慢指针
143. 重排链表	中等	链表重排
61. 旋转链表	中等	链表操作

本文作者: HGNULB

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