/**
 * 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) {

        if(head==nullptr){
            return nullptr;
        }

        vector<int> lesser;
        vector<int> greater;

        auto iter=head;
        while(iter!=nullptr){

            if(iter->val<x){
                lesser.push_back(iter->val);
            }else{
                greater.push_back(iter->val);
            }
            iter=iter->next;
        }

        ListNode* ans;

        ListNode* tail;
        ans=tail;
        int g_i=0;
        if(lesser.size()!=0){
            tail=new ListNode(lesser[0]);
        }else{
            g_i=1;
            tail=new ListNode(greater[0]);
        }

        for(int i=1;i<lesser.size();i++){
            cout<<lesser[i]<<' ';
            ListNode* node=new ListNode(lesser[i]);
            tail->next=node;
            tail=tail->next;
        }

        for(;g_i<greater.size();g_i++){
            cout<<greater[g_i]<<' ';
            ListNode* node=new ListNode(greater[g_i]);
            tail->next=node;
            tail=tail->next;
        }

        return ans;

    }
};