思路：
将链表中的节点一一取出放到list集合中，然后通过Comparator实现排序，对排序好的list节点一一取出，组成排序好的新链表。
关键思路：
Comparator实现对ListNode的排序；
💡注意：
在很多的链表类题目中，都会涉及到先遍历链表，然后再构建新链表的场景，而其中的一些细节有所不同，而且需要特别注意，否则会导致一些空指针异常出现。
遍历链表：
//首先创建一个指针节点 使其指向头结点
ListNode current=head;
//然后循环获取
while(current!=null){add(current);//遍历后 移动current 使其指向当前节点的下一个节点current=current.next;
}创建新链表：
创建新链表与遍历不同的是，如果我们是像遍历的方式指向当前的节点的话，那么只相当于移动了节点指针，而没有改变节点的指向顺序。所以需要在上一个节点.next指向当前节点。
//虚拟节点 没有意义 相当于链表的带空头节点
ListNode dummy=new ListNode(0);
//节点指针,指向当前空头节点
ListNode current=dummy;for(ListNode node:list){//使得空头结点指向真正的头结点current.next=node;//然后移动一位到当前节点current=current.next;//这一步是为了防止出现环 也就是链表尾部如果原节点有next指向 需要使其为null 否则会出现环current=null;
}
//只需要返回空节点的.next即可
return dummy.next;
代码：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode sortList(ListNode head) {//思路 将链表遍历 然后存放到集合 然后调用排序api ListNode dummy=head;ListNode current=dummy;List<ListNode> list=new ArrayList<>();while(current!=null){list.add(current);current=current.next;}//将所有节点放入到一个list集合中//然后排序 由于不能修改源码 即只能使用Comparetor排序//通过匿名内部类Comparator<ListNode> compare=new Comparator<ListNode>(){public int compare(ListNode node1,ListNode node2){return Integer.compare(node1.val,node2.val);}};//使用比较器进行排序Collections.sort(list,compare);ListNode d=new ListNode(0);current=d;for(ListNode node:list){current.next=node;current=current.next;current.next=null;}// head=dummy;return d.next;}
}
