Following are the requirements for the Partition List LeetCode challenge:
“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”.
The URL for the challenge: https://leetcode.com/problems/partition-list/
Following is a screen capture of the Eclipse IDE using the sample data provided by the challenge:
display <<< list: 1->4->3->2->5->2
display <<< list: 1->2->2->4->3->5
Please note that the solution did not include displaying the values. The display comes from my test code.
I spent time understanding the requirements and generating test code. For 
the code it seems that we could insert in a queue holding the order in which they are presented all values that are less than the x (e.g., 3). In a second queue we could insert the rest of the values preserving their order. We could then append the contents of the second to the first queue.
Following is the Java code for the entire solution:
/*
*
*/
class ListNode {
// **** members ****
int val;
ListNode next;
/*
* constructor
*/
public ListNode(int x) {
val = x;
}
/*
* build list
*/
public ListNode build(ListNode head, String vals) {
ListNode t = head;
for (int i = 0; i < vals.length(); i++) {
int val = Integer.parseInt(vals.substring(i, i + 1));
ListNode node = new ListNode(val);
t.next = node;
t = node;
}
return head;
}
/*
* display list
*/
public void display(ListNode head) {
System.out.print(“display <<< list: “);
for ( ; head != null; head = head.next) {
if (head.next != null) {
System.out.print(head.val + “->”);
} else {
System.out.print(head.val);
}
}
System.out.println();
}
}
/*
*
*/
public class Solution {
/*
* Partition the list.
*/
static ListNode partition(ListNode head, int x) {
ListNode lt = null;
ListNode ltTail = null;
ListNode r = null;
ListNode rTail = null;
// **** traverse the main list inserting nodes in auxiliary lists as needed ****
while (head != null) {
// **** insert node into lt list ****
if (head.val < x) {
if (lt == null) {
lt = head;
ltTail = lt;
head = head.next;
ltTail.next = null;
} else {
ltTail.next = head;
ltTail = ltTail.next;
head = head.next;
ltTail.next = null;
}
}
// **** insert node into r list ****
else {
if (r == null) {
r = head;
rTail = r;
head = head.next;
rTail.next = null;
} else {
rTail.next = head;
rTail = rTail.next;
head = head.next;
rTail.next = null;
}
}
}
// **** append the rest to the lt list ****
while (r != null) {
if (lt == null) {
lt = r;
ltTail = lt;
r = r.next;
ltTail.next = null;
} else {
ltTail.next = r;
ltTail = ltTail.next;
r = r.next;
ltTail.next = null;
}
}
// **** return complete list ****’
return lt;
}
/*
* Test code.
*/
public static void main(String[] args) {
// **** build and display list ****
ListNode head = new ListNode(1);
head = head.build(head, “43252”);
head.display(head);
// **** partition and display list ****
head = partition(head, 3);
head.display(head);
}
}
I am planning on creating a ListNode class with all the features needed to manipulate single linked lists. I will then use that class to create tests quicker and better that what I did in this case.
If you have comments or questions regarding this post please do not hesitate and send me a message. I will not use your name unless you explicitly allow me to do so.
John
john.canessa@gmail.com
Follow me on Twitter: @john_canessa