# My C++ solution (10ms) two versions (one maintains a single list and the other maintains two )

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

class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode *lastLNode, *lastGENode, *curNode, *newGENode ;

``````    lastLNode = curNode = &dummyHead;
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;
}
}

}
``````

};

// 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;
}