/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    ListNode* cow_partition(ListNode* head, int x) {
        /*定义一个大链表big_list保存大于 x 的节点*/
        auto* big_list = new ListNode{0};
        /*定义一个小链表sim_list保存小于 x 的节点*/
        auto* sim_list = new ListNode{0};
        ListNode* big_head = big_list;
        ListNode* sim_head = sim_list;
        while(head != nullptr) {
            if(head->val < x) {
                sim_head->next = head;
                sim_head = sim_head->next;
            }
            else {
                big_head->next = head;
                big_head = big_head->next;
            }
            head = head->next;
        }
        /*最后让小链表指向大链表表头*/
        sim_head->next = big_list->next;
        big_head->next = nullptr;

        return sim_list->next;
    }
};

题目要求实现链表所有「值 <x 节点」出现在「值 ≥x 节点」前面，那我们就可以用一个小链表保存所有小于x的节点，一个大连表保存所有大于x的节点，最后返回小链表就行了。

复杂度

• 时间复杂度:

时间复杂度,： O(n)

• 空间复杂度:

空间复杂度,： O(1)