算法笔记：力扣148. 排序链表

思路：

将链表中的节点一一取出放到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;
        

    }
}