题解 | #牛的品种排序IV#

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

题目分析：这道题常规操作就是定义两个头结点，一个头插0结点，另一个头插1节点，然后将两个链表连接起来；也可以定义一个头结点，记录第一个0结点插入的位置，在头结点后面插0结点，在第一个0结点后插1结点，两种思路大致一样。

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

ListNode* sortCowsIV(ListNode* head)
{
    // write code here
    ListNode newhead(-1);
    newhead.next = nullptr;
    ListNode* end = &newhead; //记录第一个0结点插入的位置
    int i = 1;

    ListNode* cur = head;
    while (cur)
    {
        ListNode* next = cur->next;
        if (cur->val == 0)
        {
            cur->next = newhead.next;
            newhead.next = cur;

            if (i)  //记录第一次0的位置
            {
                end = cur;
                --i;
            }
        }
        else
        {
            cur->next = end->next;
            end->next = cur;
        }
    }
    return newhead.next;
}