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

1. 题目考察的知识点

考察链表的基本操作

2. 题目解答方法的文字分析

算法思想:建立两个链表，分别收集值为1和值为0的结点，最后将这两个链表连在一起。

算法步骤： 1、建立哑结点oneDummy和zeroDummy，以便实现头插法来插入结点，创建tail结点来标识zeroDummy链表的尾巴。以便后续oneDummy和zeroDummy的结合 2、用cur结点遍历原链表，通过判断cur.val的值，来决定将cur结点插入oneDummy还是zeroDummy。 3、重复第二步，直到cur==null. 4、合并oneDummy和zeroDummy。即为答案

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode sortCowsIV (ListNode head) {
        //链表结点为空或者只有一个，则直接返回
        if(head==null||head.next==null)
        return head;
       //值为1的所有结点都在链表oneDummy中
       ListNode oneDummy = new ListNode(-1);
       //标注链表zeroDummy的尾巴结点
        ListNode tail = new ListNode(-1);
      //值为0的所有结点都在链表zeroDummy中
       ListNode zeroDummy = new ListNode(-2);
       ListNode cur = head;
       while(cur!=null){
        if(cur.val==1){
          //头插法，将值为1的结点插入到oneDummy链表中
          ListNode pre = oneDummy.next;
          oneDummy.next=cur;
          cur = cur.next;
          oneDummy.next.next = pre;
        }else{
          //头插法，将值为0的结点插入到zeroDummy链表中
          ListNode pre = zeroDummy.next;
          zeroDummy.next=cur;
          cur = cur.next;
          zeroDummy.next.next = pre;
        }
        if(zeroDummy.next!=null&&zeroDummy.next.next==null){
            tail = zeroDummy.next;
        }
        
       }
       //连接zeroDummy和oneDummy
       tail.next=oneDummy.next;
       return zeroDummy.next;
    }
}