Skip to content

Commit 1ed848f

Browse files
coderbeancoderbean
committed
0086. Partition List
1 parent b917e34 commit 1ed848f

4 files changed

Lines changed: 190 additions & 0 deletions

File tree

‎src/main/java/leetcode/0086. Partition List.md‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
### [86\. Partition List](https://leetcode.com/problems/partition-list/)
2+
3+
Difficulty: **Medium**
4+
5+
6+
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_.
7+
8+
You should preserve the original relative order of the nodes in each of the two partitions.
9+
10+
**Example:**
11+
12+
```
13+
Input: head = 1->4->3->2->5->2, x = 3
14+
Output: 1->2->2->4->3->5
15+
```
16+
17+
18+
#### Solution
19+
20+
Language: **Java**
21+
22+
```java
23+
/**
24+
* Definition for singly-linked list.
25+
* public class ListNode {
26+
* int val;
27+
* ListNode next;
28+
* ListNode(int x) { val = x; }
29+
* }
30+
*/
31+
class Solution {
32+
   public ListNode partition(ListNode head, int x) {
33+
       if (head == null || head.next == null) {
34+
           return head;
35+
      }
36+
       ListNode fakeHeader = new ListNode(0);
37+
       fakeHeader.next = head;
38+
       ListNode curr = fakeHeader;
39+
       ListNode cutPoint = null;
40+
       while (curr.next != null) {
41+
           if (curr.next.val >= x) {
42+
               if (cutPoint == null) {
43+
                   cutPoint = curr;
44+
              }
45+
               curr = curr.next;
46+
          } else if (cutPoint != null) {
47+
               ListNode node = curr.next;
48+
               curr.next = node.next;
49+
               node.next = cutPoint.next;
50+
               cutPoint.next = node;
51+
               cutPoint = node;
52+
          } else {
53+
               curr = curr.next;
54+
          }
55+
      }
56+
       return fakeHeader.next;
57+
  }
58+
}
59+
```
60+
![pic](https://raw.githubusercontent.com/PicGoBed/PicBed/master/2019-08-01-ACf21S.jpg)

‎src/main/java/leetcode/_86_/Main.java‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package leetcode._86_;
2+
3+
import leetcode.common.ListNode;
4+
5+
/**
6+
* Created by zhangbo54 on 2019-03-04.
7+
*/
8+
public class Main {
9+
public static void main(String[] args) {
10+
Solution solution = new Solution();
11+
12+
ListNode node1 = new ListNode(1);
13+
ListNode node2 = new ListNode(4);
14+
ListNode node31 = new ListNode(3);
15+
ListNode node32 = new ListNode(2);
16+
ListNode node41 = new ListNode(5);
17+
ListNode node42 = new ListNode(2);
18+
ListNode node5 = new ListNode(2);
19+
node1.next = node2;
20+
node2.next = node31;
21+
node31.next = node32;
22+
node32.next = node41;
23+
node41.next = node42;
24+
node42.next = node5;
25+
26+
27+
System.out.println(solution.partition(node1, 3));
28+
}
29+
}
30+

‎src/main/java/leetcode/_86_/Solution.java‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package leetcode._86_;
2+
3+
import leetcode.common.ListNode;
4+
5+
/**
6+
* Definition for singly-linked list.
7+
* public class ListNode {
8+
* int val;
9+
* ListNode next;
10+
* ListNode(int x) { val = x; }
11+
* }
12+
*/
13+
class Solution {
14+
public ListNode partition(ListNode head, int x) {
15+
if (head == null || head.next == null) {
16+
return head;
17+
}
18+
ListNode fakeHeader = new ListNode(0);
19+
fakeHeader.next = head;
20+
ListNode curr = fakeHeader;
21+
ListNode cutPoint = null;
22+
while (curr.next != null) {
23+
if (curr.next.val >= x) {
24+
if (cutPoint == null) {
25+
cutPoint = curr;
26+
}
27+
curr = curr.next;
28+
} else if (cutPoint != null) {
29+
ListNode node = curr.next;
30+
curr.next = node.next;
31+
node.next = cutPoint.next;
32+
cutPoint.next = node;
33+
cutPoint = node;
34+
} else {
35+
curr = curr.next;
36+
}
37+
}
38+
return fakeHeader.next;
39+
}
40+
}

‎src/main/java/leetcode/_86_/solution.md‎

Lines changed: 60 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,60 @@
1+
### [86\. Partition List](https://leetcode.com/problems/partition-list/)
2+
3+
Difficulty: **Medium**
4+
5+
6+
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_.
7+
8+
You should preserve the original relative order of the nodes in each of the two partitions.
9+
10+
**Example:**
11+
12+
```
13+
Input: head = 1->4->3->2->5->2, x = 3
14+
Output: 1->2->2->4->3->5
15+
```
16+
17+
18+
#### Solution
19+
20+
Language: **Java**
21+
22+
```java
23+
/**
24+
* Definition for singly-linked list.
25+
* public class ListNode {
26+
* int val;
27+
* ListNode next;
28+
* ListNode(int x) { val = x; }
29+
* }
30+
*/
31+
class Solution {
32+
   public ListNode partition(ListNode head, int x) {
33+
       if (head == null || head.next == null) {
34+
           return head;
35+
      }
36+
       ListNode fakeHeader = new ListNode(0);
37+
       fakeHeader.next = head;
38+
       ListNode curr = fakeHeader;
39+
       ListNode cutPoint = null;
40+
       while (curr.next != null) {
41+
           if (curr.next.val >= x) {
42+
               if (cutPoint == null) {
43+
                   cutPoint = curr;
44+
              }
45+
               curr = curr.next;
46+
          } else if (cutPoint != null) {
47+
               ListNode node = curr.next;
48+
               curr.next = node.next;
49+
               node.next = cutPoint.next;
50+
               cutPoint.next = node;
51+
               cutPoint = node;
52+
          } else {
53+
               curr = curr.next;
54+
          }
55+
      }
56+
       return fakeHeader.next;
57+
  }
58+
}
59+
```
60+
![pic](https://raw.githubusercontent.com/PicGoBed/PicBed/master/2019-08-01-ACf21S.jpg)

0 commit comments

Comments
 (0)