题解 | #单链表的排序#

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        List<ListNode> lists = new ArrayList<>();
        while (head != null) {
            ListNode next = head.next;
            head.next = null;
            lists.add(head);
            head = next;
        }
        while (lists.size() > 1) {
            if (lists.size() % 2 == 0) {
                List<ListNode> cur = new ArrayList<>();
                for (int i = 1 ; i < lists.size() ; i += 2) {
                   cur.add(mergeSort(lists.get(i-1),lists.get(i)));
                }
                lists = cur;
            } else {
                List<ListNode> cur = new ArrayList<>();
                for (int i = 1 ; i < lists.size() - 1; i += 2) {
                   cur.add(mergeSort(lists.get(i-1),lists.get(i)));
                }
                cur.add(lists.get(lists.size() - 1));
                lists = cur;
            }
        }
        return lists.get(0);
    }
    public ListNode mergeSort(ListNode root1,ListNode root2) {
        ListNode vHead = new ListNode(-100);
        ListNode work = vHead;
        work.next = null;
        while (root1 != null && root2 != null) {
            if (root1.val < root2.val) {
                work.next = root1;
                work = work.next;
                root1 = root1.next;
            } else {
                work.next = root2;
                work = work.next;
                root2 = root2.next;
            }
        }
        while (root1 != null) {
            work.next = root1;
            work = work.next;
            root1 = root1.next;
        }
         while (root2 != null) {
            work.next = root2;
            work = work.next;
            root2 = root2.next;
        }
        return vHead.next;
    }
}


// 归并排序的想法