LeetCode - Partition List
Problem description
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.
You should preserve the original relative order of the nodes in each of the two partitions.
Example:
1
2
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5
Analysis
This is a simple linked list problem. The general idea is to divide the list into two lists and then combine them.
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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummy = new ListNode(0);
ListNode bigger = new ListNode(0);
ListNode bp = bigger;
ListNode dp = dummy;
while (head != null){
ListNode next = head.next;
head.next = null;
if (head.val < x){
dp.next = head;
dp = dp.next;
}
else{
bp.next = head;
bp = bp.next;
}
head = next;
}
dp.next = bigger.next;
return dummy.next;
}
}
What to improve
- make sure isolate every node before inserting it.