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

本题考察链表排序的相关知识点。

解题思路：遍历链表，逐个取值后去加入到新链表中(需要重新new节点)，不能改变原先的链表结构，不然遍历顺序就乱了。

整体的过程如下所示

注意35行在内部寻找位置的遍历中控制一下循环条件

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 maxNode = new ListNode(-1), node = head, maxHead = maxNode;
        while(node!=null){
            if(node.val>=maxNode.val){
                // 新的最大节点
                maxNode.next = new ListNode(node.val);
                maxNode = maxNode.next;
            }else{
                // 中间节点
                ListNode temp = maxHead;
                ListNode pre = new ListNode(-1);
                pre.next = temp;
                while(temp.val<node.val&&temp.next!=null){ //寻找位置
                    pre = pre.next;
                    temp = temp.next;
                }
                //跳出循环的时候 temp刚好是第一个大于当前node的节点
                //pre代表前一个节点 也就是此时node的插入位置前后节点找到了
                ListNode newNode = new ListNode(node.val);
                pre.next = newNode;
                newNode.next = temp;
            }
            node = node.next; //node只管往后遍历
        }
        return maxHead.next;
    }
}