题解 | #单链表的排序#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {

        int [] num =  sort(head);
        ListNode node = new ListNode(-1);
        ListNode h = node;
        for (int i = 0; i < num.length; i++) {
            h.next = new ListNode(num[i]);
            h = h.next;
        }

        // write code here
        return node.next;
    }

    private int[] sort(ListNode head1) {
        ListNode cur = head1;
        int index = 0;

        while (cur != null) {
            cur = cur.next;
            index++;
        }
        int[] arr = new int[index];
        cur = head1;
        for (int i = 0; i < arr.length; i++) {
            arr[i] = cur.val;
            cur = cur.next;

        }
        Arrays.sort(arr);
        return arr;

    }
}
1.先将链表转为数组排序
2.然后创建一个新链表，遍历数组，将数组数字，放到新建的链表