// Single list version (seems a little bit faster)

class Solution {

public:

ListNode *partition(ListNode *head, int x) {

ListNode dummyHead(0);

ListNode *lastLNode, *lastGENode, *curNode, *newGENode ;

```
lastLNode = curNode = &dummyHead;
dummyHead.next = head;
while(curNode->next)
{
while(curNode->next && curNode->next->val >= x) curNode = curNode->next; // find the last Greater or equal (GE) node;
lastGENode = curNode;
while(curNode->next && curNode->next->val < x) curNode = curNode->next; // find the new last Less (L) node;
if(lastGENode == lastLNode) lastLNode = curNode; // for the first iteration, there might be no GE nodes at the beginning of the list, then we just update lastLNode
else
{ // otherwise, we need to cut the sub-linK (with nodes less than x) from lastGENode->next to curNode and insert it to lastLNode->next and current->next
newGENode = curNode->next;
curNode->next = lastLNode->next;
lastLNode->next = lastGENode->next;
lastGENode->next = newGENode;
lastLNode = curNode;
curNode = lastGENode;
}
}
return dummyHead.next;
}
```

};

// two lists version (much simpler)

```
ListNode LHead(0), RHead(0);
ListNode *curNode = head, *LPt = &LHead, *RPt = &RHead;
while(curNode)
{
if(curNode->val < x) {LPt = (LPt->next = curNode);}
else {RPt = (RPt->next = curNode);}
curNode = curNode->next;
}
LPt->next = RHead.next;
RPt->next = NULL;
return LHead.next;
}
```