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

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) {
        // write code here
        if (head == null || head.next == null) {
            return head;
        }

        boolean swapped;
        do {
            swapped = false;
            ListNode current = head;
            while (current != null && current.next != null) {
                if (current.val > current.next.val) {
                    int temp = current.val;
                    current.val = current.next.val;
                    current.next.val = temp;
                    swapped = true;
                }
                current = current.next;
            }
        } while (swapped);

        return head;
    }
}

考察的知识点：

1. 链表基本概念：了解链表的定义和基本操作，比如节点插入、删除等。
2. 排序算法：了解不同的排序算法，例如冒泡排序、插入排序、快速排序等。

题目的解答方法：

在不使用库内置的 sort 函数的情况下，我们可以采用一种简单的排序方法，比如冒泡排序。冒泡排序的基本思想是，从头开始依次比较相邻的元素，如果顺序错误就交换位置，这样经过一轮遍历后，最大的元素就会“冒泡”到数组的末尾。重复执行这个过程，每次遍历都会将当前未排序部分的最大元素放到正确的位置，直到整个数组有序。

对于链表，我们可以用类似的方法来排序，具体步骤如下：

1. 遍历链表，对于每一轮遍历，从头节点开始，依次比较相邻的节点。
2. 如果当前节点的品种比下一个节点的品种大（即当前节点是白牛而下一个节点是黑牛），则交换这两个节点的内容，即交换品种。
3. 继续遍历下一个节点，直到链表末尾。
4. 重复以上步骤，直到没有需要交换的节点，此时链表就已经排好序。