题解 | #牛群分隔#

考察的知识点：与链表有关的题基本都是插入，删除，交换顺序等，解决这些问题通常将链表的指针进行修改。

问题分析：要将单链表按照大小重新排序，使大的在一边，小的在一边，所以定义两个头结点，遍历单链表，一个头结点连接大的结点，另一个头结点连接小的结点，然后再进行合并，给nullptr的给nullptr即可。

本题解析所用的编程语言：c++

ListNode* cow_partition(ListNode* head, int x)
{
    // write code here
    ListNode* headsmall = new ListNode(-1);
    ListNode* headgreat = new ListNode(-1);
    ListNode* cur = head, * cur1 = headsmall, * cur2 = headgreat;
    while (cur)
    {
        if (cur->val < x) //小的插入到headsmall
        {
            cur1->next = cur;
            cur1 = cur1->next;
        }
        else            //大的插入到headgreat
        {
            cur2->next = cur;
            cur2 = cur2->next;
        }
        cur = cur->next;
    }
    //将两个链表合并
    cur1->next = headgreat->next;
    cur2->next = nullptr;
    head = headsmall->next;
    //删除
    delete headsmall;
    delete headgreat;

    return head;
}