# One pass , O (n) , easy to follow instructions

• Essentially, we need to build 2 lists. One whose values are < than x and the other whose values are >= x. Maintain head and tail for both the list.
Drop the anchor node when a node.val > x for the first time. This anchor node is the head of the list whose values are >= x
If there is no anchor node, keep expanding the previous list.
There are 4 cases to consider

Case 1 : CurrentNode.Val < x and null == anchor node : A null anchor node means, we have not found any node whose value is >= x. So, not much to do, just expand the prev

Case 2: CurrentNode.Val > x and null == anchor node : This means, we have found our first node whose value >= x, make this the anchor node. Essentially, make this node the head of the list whose values are >= x

Case 3 : CurrentNode.Val > x and null != anchor node : Another node whose value >=x ... since anchor node is not null, just add this node to tail of the anchor node list.

Case 4 ( Most important case) : CurrentNode.Val < x and null == anchor node
This means, we need to move the current node to the list depicted by the prev and then reconnect all the node. Looks at the code to get a better understanding of all the connections

``````    public ListNode partition(ListNode head, int x) {
return null;
}

ListNode anchor = null;
ListNode anchorCur = null;

while (null != cur){

if (cur.val < x && null == anchor){
prevCur = cur;
cur = cur.next;
}else if (cur.val >= x && null == anchor){
anchor = cur;
anchorCur = anchor;
cur = cur.next;
}else if (cur.val >= x && null != anchor){
anchorCur = cur;
cur = cur.next;
}else {
ListNode nxt = cur.next;
prevCur.next = cur;
cur.next = anchor;
anchorCur.next = nxt;
cur = nxt;
prevCur = prevCur.next;
}
}