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
31
32
| class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
if (head == null || head.next == null) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy, ptr = dummy;
for (int i = 0; i < right - left + 2; i++) {
ptr = ptr.next;
}
for (int i = 0; i < left - 1; i++) {
prev = prev.next;
ptr = ptr.next;
}
ListNode start = prev.next;
prev.next = reverse(start, right - left + 1);
start.next = ptr;
return dummy.next;
}
private ListNode reverse(ListNode node, int steps) {
ListNode prev = null, curr = node;
for (int i = 0; i < steps; i++) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
|
需要sentinel node以及reverse node就行了. 这里reverse node要reverse一定个数的, 不能全reverse完, 要reverse一定的数量.
时间复杂度: O(n)
空间复杂度: O(1)
