题解 | #单链表的排序#

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
        ListNode dummy = new ListNode(-1);
        ListNode tmp =  head;
        Map<Integer,ListNode> map = new HashMap();
        
        List<ListNode> list = new ArrayList();
	   // 1. 循环链表，将链表中的每个单个节点放到list中
        while(tmp != null) {
            list.add(new ListNode(tmp.val));
            tmp = tmp.next;
        }
	  // 2. 利用ArrayList的sort函数进行排序
        list.sort((a,b) -> b.val - a.val);
	  // 3. 循环排序后的list，然后拼接成新的链表
        for(int i=0; i<list.size(); i++) {
            ListNode node = list.get(i);
            ListNode next = dummy.next;
            dummy.next = node;
            dummy.next.next = next;
        }

        return dummy.next;
    }
}