1
/**
2
 * Definition for singly-linked list. public class ListNode { int val; ListNode next; ListNode() {}
3
 * ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val;
4
 * this.next = next; } }
5
 */
6
class Solution {
7
  public ListNode sortList(ListNode head) {
8
    if (head == null || head.next == null) {
9
      return head;
10
    }
11

12
    ListNode mid = middle(head);
13

14
    ListNode left = sortList(head);
15
    ListNode right = sortList(mid);
16

17
    return mergeTwoLists(left, right);
18
  }
19

20
  public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
21
    ListNode head = new ListNode();
22
    ListNode tail = head;
23
    while (list1 != null && list2 != null) {
24
      if (list1.val < list2.val) {
25
        tail.next = list1;
26
        list1 = list1.next;
27
        tail = tail.next;
28
      } else {
29
        tail.next = list2;
30
        list2 = list2.next;
31
        tail = tail.next;
32
      }
33
    }
34

35
    tail.next = (list1 != null) ? list1 : list2;
36

37
    return head.next;
38
  }
39

40
  public ListNode middle(ListNode head) {
41
    ListNode midprev = null;
42
    while (head != null && head.next != null) {
43
      midprev = (midprev == null) ? head : midprev.next;
44
      head = head.next.next;
45
    }
46
    ListNode mid = midprev.next;
47
    midprev.next = null;
48
    return mid;
49
  }
50
}