题解 | #牛群分隔#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <cmath>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    ListNode* cow_partition(ListNode* head, int x) {
        // write code here
        // 应当保留两个分区中每个节点的初始相对位置。
        // 这个x 是指下标还是指数值呢？
        // 是数值，输入：{4,3,2,5,2},3 返回值：{2,2,4,3,5}，并没有错，
        // 因为4属于 “大于等于3” 的范围

        // 小于 x 的链表
        ListNode* min_x = new ListNode(-1);
        // 大于等于 x 的链表
        ListNode* equal_max_x = new ListNode(-1);

        // 保存 min_x 的头部
        ListNode* left = min_x;
        // 保存 equal_max_x 的头部 
        ListNode* right = equal_max_x;

        ListNode* t = head;
        while(t)
        {
            if(t->val < x)
            {
                min_x->next = new ListNode(t->val);
                min_x = min_x->next;
            }
            else 
            {
                equal_max_x->next = new ListNode(t->val);
                equal_max_x = equal_max_x->next;
            }

            t = t->next;
        }

        min_x->next = right->next;

        ListNode* ans = left->next;

        return ans;
    }
};