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

1. 题目考察的知识点

链表的插入与删除等基础操作，插入排序算法

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

插入排序的基本原理：维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加 1，直到全部元素都加入到有序序列中。

算法简单描述： 1、判断head结点是否为null或者只有一个元素，如果是，则直接返回head即可。 2、创建哑节点 dummy，令 dummy.next = head。引入哑节点是为了便于在头节点之前插入节点。 3、创建lastSorted结点，它为链表的已排序部分的最后一个节点。cur指向当下的未排序的结点，当它为空时代表，所有未排序结点已经遍历完毕。 4、要将未排序的结点插入到已经排好序的前半段链表部分，有两种情况。 一、若 lastSorted.val <= curr.val，说明 curr 应该位于 lastSorted 之后，将 lastSorted 后移一位，curr 变成新的 lastSorted。 二、从链表的头节点开始往后遍历链表中的节点，寻找插入 curr 的位置。定义prev 为插入 curr 的位置的前一个节点，以完成对 curr 的插入。 5、由于lastSorted结点，它为链表的已排序部分的最后一个节点，则lastSorted.next为最近为排序的结点，把值赋给cur.

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 sortList (ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        //插入排序
        //定义哑结点
        ListNode dummy = new ListNode(-1);
        //使用头插法
        dummy.next = head;
        //lastSorted为链表的已排序部分的最后一个节点
        ListNode cur=head.next;
        ListNode lastSorted = head;
        while(cur!=null){
          if(lastSorted.val<=cur.val){
            //若 lastSorted.val <= curr.val，说明 curr 应该位于 lastSorted 之后，将 lastSorted 后移一位，curr 变成新的 lastSorted
            lastSorted = lastSorted.next;
          }else{
            //从链表的头节点开始往后遍历链表中的节点，寻找插入 curr 的位置。令 prev 为插入 curr 的位置的前一个节点，进行如下操作，完成对 curr 的插入：

            ListNode prev =dummy;
            while(prev.next.val<=cur.val){
               prev=prev.next;
            }
            lastSorted.next=cur.next;
            cur.next=prev.next;
            prev.next = cur;
          }
          cur=lastSorted.next;
        }
        //返回头节点
      return dummy.next;
    }
}