题解 | 单链表的排序

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head==null||head.next==null){
         return head;
        }
      List<Integer> list= new ArrayList<>();
      ListNode p=head;
      while(head!=null){
         p=head.next;
         head.next=null;
         list.add(head.val);
         head=p;
      }
      Collections.sort(list);
      ListNode m=new ListNode(-1);
      ListNode q=m;
      for(int i=0;i<list.size();i++){
        m.next=new ListNode(list.get(i));
        m=m.next;
      }
      return q.next;
    //   Map<Integer,ListNode> map=  new HashMap<>();
    //   List<Integer> list= new ArrayList<>();
    //   ListNode p=head;
    //   while(head!=null){
    //      p=head.next;
    //      head.next=null;
    //      list.add(head.val);
    //      map.put(head.val,head);
    //      head=p;
    //   }
    //   Integer[] arr=new Integer[list.size()];
    //   for(int i=0;i<list.size();i++){
    //      arr[i]=list.get(i);
    //   }
    //   Arrays.sort(arr);
    //   ListNode durrmy=new ListNode(-1);
    //   ListNode start=durrmy;
    //   for(int i=0;i<list.size();i++){
    //       durrmy.next=map.get(arr[i]);
    //       durrmy=durrmy.next;
    //   }
    }
}

用直接创建节点的方式比用数据结构来的更快内存占用更小，该思路好时402毫秒；占用内存最大33m；