Repository navigation
Expand file tree
/
Copy path_92.java
More file actions
118 lines (99 loc) · 3.81 KB
/
Copy path_92.java
File metadata and controls
118 lines (99 loc) · 3.81 KB
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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
package com.fishercoder.solutions;
import com.fishercoder.common.classes.ListNode;
import com.fishercoder.common.utils.CommonUtils;
/**Reverse a linked list from position m to n. Do it in-place and in one-pass.
For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,
return 1->4->3->2->5->NULL.
Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.*/
public class _92 {
// then I turned to Discuss and find this most upvoted solution:
// https://discuss.leetcode.com/topic/8976/simple-java-solution-with-clear-explanation, it's
// indeed concise, I knew there's such a solution there
public ListNode reverseBetween_concise_version(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 ListNode reverseBetween(ListNode head, int m, int n) {
// find node at position m, let's call it "revHead"
// set its previous node as "newRevHead", then start processing until we reach node at
// position n
ListNode newRevHead = null, revHead = head, pre = new ListNode(-1);
pre.next = head;
if (m > 1) {
int mCnt = 1;
while (mCnt++ < m) {
newRevHead = revHead;
revHead = revHead.next;
}
}
ListNode node_prior_to_m = newRevHead;
// iteratively
int nCnt = m;
ListNode next = null;
while (nCnt <= n) {
next = revHead.next;
revHead.next = newRevHead;
newRevHead = revHead;
revHead = next;
nCnt++;
}
if (nCnt > n)
nCnt--;
// append next to the tail of the reversed part
ListNode reversedPart = newRevHead;
if (reversedPart != null) {
while (nCnt > m) {
reversedPart = reversedPart.next;
nCnt--;
}
reversedPart.next = next;
}
// append the reversed part head to the node at position m-1
if (node_prior_to_m != null)
node_prior_to_m.next = newRevHead;
else
pre.next = newRevHead;
return pre.next;
}
public static void main(String... strings) {
_92 test = new _92();
// ListNode head = new ListNode(1);
// head.next = new ListNode(2);
// head.next.next = new ListNode(3);
// head.next.next.next = new ListNode(4);
// head.next.next.next.next = new ListNode(5);
// int m = 2, n =4;
// ListNode head = new ListNode(5);
// int m = 1, n =1;
ListNode head = new ListNode(3);
head.next = new ListNode(5);
int m = 1, n = 2;
CommonUtils.printList(head);
ListNode result = test.reverseBetween(head, m, n);
CommonUtils.printList(result);
}
}