LeetCode 92. 反转链表 II

题目描述

✅ 92. 反转链表 II

image-20230226203819078

image-20230226203923748

思路分析

  • 找到反转链表的起始节点的前一个节点
  • 反转指定区间的链表
  • 连接左右两部分

参考代码



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30



func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if head == nil || head.Next == nil || left == right {
		return head
	}

	dummy := &ListNode{Next: head} // 创建虚拟头节点
	first := dummy

	// 移动 first 指针到需要反转部分的前一个节点
	for i := 1; i < left; i++ {
		first = first.Next
	}

	var pre *ListNode
	cur := first.Next

	// 反转从 left 到 right 的节点
	for i := left; i <= right; i++ {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	// 将反转后的部分连接回原链表
	first.Next.Next = cur
	first.Next = pre

	return dummy.Next // 返回虚拟头节点的下一个节点，即反转后的链表头节点
}
  • 时间复杂度：O (n)，其中 n 是链表的长度。
  • 空间复杂度：O (1)，只使用了常数级别的额外空间。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25



func reverseBetween(head *ListNode, left int, right int) *ListNode {
	if head == nil || head.Next == nil || left == right {
		return head
	}

	dummy := &ListNode{Next: head}
	first := dummy
	for i := 1; i < left; i++ {
		first = first.Next
	}

	var pre *ListNode
	cur := first.Next
	for i := left; i <= right; i++ {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}

	first.Next.Next = cur
	first.Next = pre

	return dummy.Next
}
  • 时间复杂度：O (n)，其中 n 是链表的长度。
  • 空间复杂度：O (1)，只使用了常数级别的额外空间。

➡️ 点击查看 Java 题解



1



write your code here
本文作者:
本文链接: https://hgnulb.github.io/blog/2025/92836975
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！