LeetCode 92. 反转链表 II
题目描述
思路分析
- 找到反转链表的起始节点的前一个节点
- 反转指定区间的链表
- 连接左右两部分
参考代码
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 // 返回虚拟头节点的下一个节点,即反转后的链表头节点
}
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
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head == null || head.next == null || left >= right) {
return head;
}
ListNode dummy = new ListNode();
dummy.next = head;
ListNode start = dummy;
for (int i = 1; i < left; i++) {
start = start.next;
}
ListNode pre = null, cur = start.next;
for (int i = left; i <= right; i++) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
start.next.next = cur;
start.next = pre;
return dummy.next;
}
}
相似题目
题目 | 难度 | 题解 |
---|---|---|
反转链表 | Easy |
CC BY-NC-SA 4.0
许可协议,转载请注明出处!
本博客所有文章除特别声明外,均采用