/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        // head->1->4->3->2->5->2

        ListNode* curr = head;
        ListNode* less_head = new ListNode(0); // dummy node (node < x)
        ListNode* less_tail = less_head; // less tail pointer
        ListNode* large_head = new ListNode(0); // dummy node (node >= x)
        ListNode* large_tail = large_head; // large tail pointer

        while (curr != nullptr){
            if (curr -> val < x){
                less_tail -> next = new ListNode(curr -> val);
                less_tail = less_tail -> next; // move tail pointer
            } else{
                large_tail -> next = new ListNode(curr -> val);
                large_tail = large_tail -> next; // move tail pointer
            }
            curr = curr -> next; // to the next node
        }

        // result
        // less_head->0->1->2->2
        // large_head->0->4->3->5

        less_tail -> next = large_head -> next;
        // concatenate less and large List
        // less_head->0->1->2->2->4->3->5        

        return less_head -> next;
        // 1->2->2->4->3->5
    }
};