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

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

问题分析：

• 可采用归并排序法,将链表递归二分再排序将头节点返回作为下一次排序的参数
• 或创建虚拟头节点,将当前节点从头遍历比较,找到位置插入即可返回虚拟头节点的next

本题解析所用的编程语言：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 left = head;
        ListNode right = split(head);
        return mergeList(sortList(left), sortList(right));
    }

    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;
    }

    private ListNode split(ListNode head){
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null)
        {
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;          //断尾
        return mid;
    }
}