题解 | #牛群的身高排序#

题目考察的知识点是：

本题主要考察的是快速排序、链表。

题目解答方法的文字分析：

这道题本意就是对单链表进行排序，第一种方法就是新建一个结点，进行头插，遍历，比较，排序，时间复杂度为O(n^2)；第二种方法是**归并排序** ，归并排序说简单些就是将一堆n个数分成n个块，然后将n个块弄成大点的n/2个块，直到合成一个块。

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

java语言。

完整且正确的编程代码：

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 sortList (ListNode head) {
        // write code here
        if (head == null || head.next == null) return head;
        ListNode slow = head, fast = head.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode newNode = slow.next;
        slow.next = null;
        return mergeList(sortList(head), sortList(newNode));
    }

    public ListNode mergeList(ListNode list1, ListNode list2) {
        ListNode dummyNode  = new ListNode(-1), p = dummyNode;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                p.next = list2;
                list2 = list2.next;
            } else {
                p.next = list1;
                list1 = list1.next;
            }
            p = p.next;
        }
        if (list1 != null) p.next = list1;
        if (list2 != null) p.next = list2;
        return dummyNode.next;
    }

}