Partition List

• Time : $O(n)$
• Space : $O(1)$

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* Solution::partition(ListNode* A, int B) {
    ListNode* less = new ListNode(-1);
    ListNode* greater = new ListNode(-1);
    ListNode* lrunner = less;
    ListNode* grunner = greater;
    while(A) {
        if(A->val < B) {
            lrunner->next = A;
            lrunner = lrunner->next;
        } else {
            grunner->next = A;
            grunner = grunner->next;
        }
        A = A->next;
        grunner->next = NULL;
        lrunner->next = NULL;
    }
    lrunner->next = greater->next;
    return less->next;
}