forked from fishercoder1534/Leetcode
-
Notifications
You must be signed in to change notification settings - Fork 1
/
_92.java
71 lines (65 loc) · 2.48 KB
/
_92.java
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
package com.fishercoder.solutions;
import com.fishercoder.common.classes.ListNode;
public class _92 {
public static class Solution1 {
/**
* credit: https://discuss.leetcode.com/topic/8976/simple-java-solution-with-clear-explanation
*/
public ListNode reverseBetween(ListNode head, int m, int n) {
// use four nodes, pre, start, then, dummy
// just reverse the nodes along the way
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode pre = dummy;
for (int i = 0; i < m - 1; i++) {
pre = pre.next;
}
ListNode start = pre.next;// start is the node prior to reversing, in the given example,
// start is node with value 1
ListNode then = start.next;// then is the node that we'll start to reverse, in the given
// example, it's 2
for (int i = 0; i < n - m; i++) {
// pay special attention to this for loop, it's assigning then.next to start.next, it
// didn't initialize a new node
// this does exactly what I desired to do, but I just didn't figure out how to implement
// it, thumbs up to the OP!
start.next = then.next;
then.next = pre.next;
pre.next = then;
then = start.next;
}
return dummy.next;
}
}
public static class Solution2 {
/**
* My completely original solution on 10/25/2021.
*/
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode pre = new ListNode(-1);
pre.next = head;
ListNode tmp = pre;
right -= left;
while (left-- > 1 && tmp != null) {
tmp = tmp.next;
}
ListNode intersection = tmp;
ListNode reverseHead = tmp.next;
ListNode prev = null;
right++;
int original = right;
while (right-- > 0 && reverseHead != null) {
ListNode next = reverseHead.next;
reverseHead.next = prev;
prev = reverseHead;
reverseHead = next;
}
intersection.next = prev;
while (original-- > 0) {
intersection = intersection.next;
}
intersection.next = reverseHead;
return pre.next;
}
}
}