题解 | #牛群分隔#

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察的主要知识点是链表操作，如何在保持节点相对位置的前提下，按照给定条件对链表进行分割。

题目解答方法的文字分析

我们需要将链表中小于给定值 x 的节点放在大于等于 x 的节点之前，同时保持节点的相对位置不变。可以使用两个链表分别存储小于 x 和大于等于 x 的节点，然后将两个链表连接起来。

思路步骤如下：

1. 创建两个新链表，一个用于存储小于 x 的节点（记为smaller），一个用于存储大于等于 x 的节点（记为greater）。
2. 遍历原始链表，将小于 x 的节点连接到smaller链表上，将大于等于 x 的节点连接到greater链表上。
3. 将smaller链表的尾节点连接到greater链表的头节点，这样就得到了分割后的链表。
4. 返回新链表的头节点即可。

本题解析所用的编程语言

本题解析所用的编程语言是C++。

完整且正确的编程代码

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param x int整型 
     * @return ListNode类
     */
    ListNode* cow_partition(ListNode* head, int x) {
        ListNode* smaller_head = new ListNode(0); // 虚拟头节点，用于存储小于 x 的节点
        ListNode* greater_head = new ListNode(0); // 虚拟头节点，用于存储大于等于 x 的节点
        ListNode* smaller = smaller_head;
        ListNode* greater = greater_head;
        
        while (head) {
            if (head->val < x) {
                smaller->next = head;
                smaller = smaller->next;
            } else {
                greater->next = head;
                greater = greater->next;
            }
            head = head->next;
        }
        
        // 连接两个链表
        smaller->next = greater_head->next;
        greater->next = nullptr; // 结尾置空
        
        ListNode* result = smaller_head->next;
        delete smaller_head; // 释放虚拟头节点内存
        delete greater_head; // 释放虚拟头节点内存
        
        return result;
    }
};

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！