C++ | Another approach | Without creating dummy nodes | O(n) Time and O(1) Space


#1
ListNode* Solution::partition(ListNode* A, int B) {
if(!A || !A->next) return A;
ListNode* prev = NULL; // For storing prev to great
ListNode* great = A; // For storing the first node with value >= B
if(great->val < B){
    while(great->next->val < B){
        great = great->next;
    }
    prev = great;
    great = great->next;
}

ListNode* ptr = great;
ListNode* node = NULL;
ListNode* head = NULL;

if(prev) head = A; //When great is the not the first node set head as A.

while(ptr->next){
    if(ptr->next->val < B){
        node = ptr->next->next;
        if(prev){
            ptr->next->next = prev->next;
            prev->next = ptr->next;
            prev = prev->next;
        }
        else{
            // This is the condition when great is the first node
            ptr->next->next = great;
            great = ptr->next;
            prev = great;
            // When great is first node, and there exists a node after great which is less than B make that node as head.
            head = prev; 
        }
        ptr->next = node;
    }
    else ptr = ptr->next;
}

if(!prev && !head) head = great; // For cases when the list is sorted and great is first node.
return head;

}