#include <iostream>
using namespace std;
#include <cstdlib>
#include <ctime>
#include <vector>

 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 == NULL) return head;  // 空链表直接返回
        ListNode *dummy = new ListNode(-1), *p = dummy;
        ListNode *h0 = new ListNode(-1); //创建虚拟节点，其后继为输入的头结点
        h0->next = head; //其后继为输入的头结点
        ListNode *h = h0; //h0的后继将成为新的头结点并输出返回，因此不方便直接操作h0
        // ListNode *tail;
        while (h->next != NULL)
        {   
            // tail = h->next;
            if(h->next->val >= x)// 是我们想要的数
            {
                ListNode *temp = h->next;  // 留住想要的数
                h->next = h->next->next; ////更新h的后继
                p->next = temp;  // 用一个头指向想要的节点
                temp->next = NULL; //节点尾给上空值
                p = temp; //更新p节点位置
            } 
            else
            {
                h = h->next;//不是我们想要的数 往右走
            } 
        }
        h->next = dummy->next;
        return h0->next;
    }
};

int main()
{
    ListNode *head = new ListNode(2);
    // head->val = rand()%10;
    ListNode *q = head;
    // srand(time(NULL)); // 初始化随机数发生器   
    // for(int i = 0; i < 5; i++)
    // {
    //     ListNode *node = new ListNode;
    //     q->next = node;
    //     node->val = rand()%10;
    //     node->next = NULL;
    //     q = node;
    // }

    // vector<int> nums = {3,4,3,2,5,2};  // 创建列表
    vector<int> nums = {2,1};  // 创建列表
    for(int i = 1; i < nums.size(); i++)
    {
        q->next = new ListNode(nums[i]);
        q = q->next;
    }


    ListNode *p = head;
    while (p != NULL) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
    Solution s;
    p = s.partition(head, 2);
    while (p != NULL) 
    {
        cout << p->val << " ";
        p = p->next;
    }


}