# Question

Formatted question description: https://leetcode.ca/all/86.html

86	Partition List

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.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.



# Algorithm

All nodes less than the given value are taken out to form a new linked list. At this time, the values of the remaining nodes in the original linked list are greater than or equal to the given value, as long as the original linked list is directly connected to the new linked list.

Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2
New:

Original: 4 -> 3 -> 2 -> 5 -> 2
New:　  1

Original: 4 -> 3 -> 5 -> 2
New:　  1 -> 2

Original: 4 -> 3 -> 5
New:　  1 -> 2 -> 2

Original:
New:　  1 -> 2 -> 2 -> 4 -> 3 -> 5



# Code

Java

• 
public class Partition_List {

/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode partition(ListNode head, int x) {
}

ListNode lessList = new ListNode(0);
ListNode moreList = new ListNode(0);

int xCount = 0;
while (current != null) {
int num = current.val;

if (num < x) {
lessList.next = new ListNode(num);
lessList = lessList.next;
} else {
moreList.next = new ListNode(num);
moreList = moreList.next;
}

current = current.next;
}

// append target x
while (xCount > 0) {
lessList.next = new ListNode(x);
lessList = lessList.next;

xCount--;
}

// connect two lists

}
}

}

• // OJ: https://leetcode.com/problems/partition-list/
// Time: O(N)
// Space: O(1)
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
if (p->val < x) {
ltTail->next = p;
ltTail = p;
} else {
geTail->next = p;
geTail = p;
}
}
geTail->next = NULL;
}
};

• # Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type x: int
:rtype: ListNode
"""
return None
dummy = ListNode(-1)
p = dummy
while p and p.next:
if p.next.val < x:
sDummy.next = p.next
p.next = p.next.next
sDummy = sDummy.next
else:
p = p.next
# if you change p.next then make sure you wouldn't change p in next run
sDummy.next = dummy.next