Skip to content

Commit 633abea

Browse files
fishercoder1534fishercoder1534
committed
edit 86
1 parent cbbde4f commit 633abea

File tree

2 files changed

+19
-165
lines changed

2 files changed

+19
-165
lines changed

‎README.md

+1-1
Original file line numberDiff line numberDiff line change
@@ -481,7 +481,7 @@ Your ideas/fixes/algorithms are more than welcome!
481481
|89|[Gray Code](https://leetcode.com/problems/gray-code/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_89.java)|O(n) |O(1)|Medium|Bit Manipulation
482482
|88|[Merge Sorted Array](https://leetcode.com/problems/merge-sorted-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_88.java)|O(max(m,n)) |O(1)|Easy|
483483
|87|[Scramble String](https://leetcode.com/problems/scramble-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_87.java)|O(?) |O(?)|Hard| Recursion
484-
|86|[Partition List](https://leetcode.com/problems/partition-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_86.java)|O(?) |O(?)|Medium|
484+
|86|[Partition List](https://leetcode.com/problems/partition-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_86.java)|O(n) |O(1)|Medium|
485485
|85|[Maximal Rectangle](https://leetcode.com/problems/maximal-rectangle/)|[Solution](../master/src/main/java/com/fishercoder/solutions/MaximalRectangle.java)|O(m*n) |O(n)|Hard|DP
486486
|84|[Largest Rectangle in Histogram](https://leetcode.com/problems/largest-rectangle-in-histogram/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_84.java)|O(n) |O(n)|Hard|Array, Stack
487487
|83|[Remove Duplicates from Sorted List](https://leetcode.com/problems/remove-duplicates-from-sorted-list/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_83.java)|O(n) |O(1)|Medium| Linked List

‎src/main/java/com/fishercoder/solutions/_86.java

+18-164
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,8 @@
33
import com.fishercoder.common.classes.ListNode;
44

55
/**
6+
* 86. Partition List
7+
*
68
* Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
79
810
You should preserve the original relative order of the nodes in each of the two partitions.
@@ -14,172 +16,24 @@
1416
public class _86 {
1517

1618
public ListNode partition(ListNode head, int x) {
17-
if(head == null){
18-
return head;
19-
}
20-
else{
21-
ListNode keeper, detector, detPre, keepNxt, myHead;/* initialize two pointers, "keeper" is used to
22-
indicate where the next node that is smaller than x should be appended while
23-
detector moves in the forefront to detect whether each node is smaller than x */
24-
detector = head;
25-
keeper = head;
26-
detPre = head;
27-
keepNxt = head;
28-
myHead = new ListNode(Integer.MAX_VALUE);
29-
myHead.next = head;
30-
31-
if(head.val >= x){
32-
keeper = myHead;
33-
34-
/* we use two while loops:
35-
* first one to locate where the initial position of keeper should be;
36-
* second one to start traversing the whole linkedlist */
37-
while(detector != null){
38-
/* first while loop*/
39-
if(detector.val < x){
40-
detPre.next = detector.next;
41-
keeper = detector;
42-
keeper.next = head;
43-
keepNxt = keeper.next;
44-
myHead = keeper;
45-
detector = detPre.next;
46-
break;
47-
}
48-
else{
49-
if(detector.next != null){
50-
detPre = detector;
51-
detector = detector.next;
52-
}
53-
else{
54-
break;
55-
}
56-
}
57-
}
58-
59-
while(detector != null){
60-
/* second while loop */
61-
if(detector.val >= x){
62-
if(detector.next != null){
63-
detPre = detector;
64-
detector = detector.next;
65-
}
66-
else{
67-
if(Integer.MAX_VALUE == myHead.val){
68-
myHead = myHead.next;
69-
}
70-
else
71-
break;
72-
}
73-
}
74-
else{
75-
if(detector.next != null){
76-
detPre.next = detector.next;
77-
keeper.next = detector;
78-
keeper.next.next = keepNxt;
79-
detector = detPre.next;
80-
81-
/* then I'll have to update the keeper pointer and keepNxt pointer*/
82-
keeper = keeper.next;
83-
keepNxt = keeper.next;
84-
}
85-
else{
86-
keeper.next = detector;
87-
keeper.next.next = keepNxt;
88-
detPre.next = null;
89-
break;
90-
}
91-
}
92-
System.out.println("\nIn second while loop: keeper.val = " + keeper.val + "\tkeepNxt.val = " + keepNxt.val + "\tdetector.val = " + detector.val
93-
+ "\tdetPre.val = " + detPre.val);
94-
}
95-
System.out.println();
96-
ListNode temp = myHead;
97-
while(temp != null){
98-
System.out.print(temp.val);
99-
temp = temp.next;
100-
}
101-
return myHead;
102-
}
103-
else{/* when the very first node is greater or equal than x */
104-
105-
/* we use two while loops:
106-
* first one to locate where the initial position of keeper should be;
107-
* second one to start traversing the whole linkedlist */
108-
while(detector != null ){
109-
/* first while loop*/
110-
if(detector.val >= x){
111-
break;
112-
}
113-
else{
114-
keeper = detector;
115-
detector = detector.next;
116-
}
117-
}
118-
if(detector != null){
119-
detPre = keeper;
120-
keepNxt = keeper.next;
121-
while(detector != null){
122-
/* second while loop */
123-
if(detector.val >= x){
124-
if(detector.next != null){
125-
detPre = detector;
126-
detector = detector.next;
127-
}
128-
else{
129-
break;
130-
}
131-
}
132-
else{
133-
if(detector.next != null){
134-
detPre.next = detector.next;
135-
keeper.next = detector;
136-
keeper.next.next = keepNxt;
137-
detector = detPre.next;
138-
139-
/* then I'll have to update the keeper pointer and keepNxt pointer*/
140-
keeper = keeper.next;
141-
keepNxt = keeper.next;
142-
}
143-
else{
144-
keeper.next = detector;
145-
keeper.next.next = keepNxt;
146-
detPre.next = null;
147-
break;
148-
}
149-
}
150-
System.out.println("\nIn second while loop: keeper.val = " + keeper.val + "\tkeepNxt.val = " + keepNxt.val + "\tdetector.val = " + detector.val
151-
+ "\tdetPre.val = " + detPre.val);
152-
ListNode temp = head;
153-
while(temp != null){
154-
System.out.print(temp.val);
155-
temp = temp.next;
156-
}
157-
}
158-
System.out.println();
159-
ListNode temp = head;
160-
while(temp != null){
161-
System.out.print(temp.val);
162-
temp = temp.next;
163-
}
164-
return head;
165-
}
166-
else if(detector == null){
167-
System.out.println("\nIn second while loop: keeper.val = " + keeper.val + "\tkeepNxt.val = " + keepNxt.val + "\tdetPre.val = " + detPre.val);
168-
ListNode temp = head;
169-
while(temp != null){
170-
System.out.print(temp.val);
171-
temp = temp.next;
172-
}
173-
return head;
174-
}
175-
}
176-
ListNode temp = head;
177-
while(temp != null){
178-
System.out.print(temp.val);
179-
temp = temp.next;
19+
if (head == null || head.next == null) return head;
20+
ListNode left = new ListNode(0);
21+
ListNode right = new ListNode(0);
22+
ListNode less = left;
23+
ListNode greater = right;
24+
while (head != null) {
25+
if (head.val < x) {
26+
less.next = head;
27+
less = less.next;
28+
} else {
29+
greater.next = head;
30+
greater = greater.next;
18031
}
181-
return head;
32+
head = head.next;
18233
}
34+
greater.next = null;
35+
less.next = right.next;
36+
return left.next;
18337
}
18438

18539
}

0 commit comments

Comments
 (0)