1 public class Solution {
 2     public ListNode sortList(ListNode head) {
 3         if (head == null || head.next == null) {
 4             return head;
 5         }
 6         ListNode mid = findMid(head);
 7         ListNode second = sortList(mid.next);
 8         mid.next = null;
 9         ListNode first = sortList(head);
10         return merge(first, second); 
11     }
12     private ListNode findMid(ListNode head) {
13         if (head == null || head.next == null) {
14             return head;
15         }
16         ListNode slow = head, fast = head;
17 
18         while (fast.next != null && fast.next.next != null) {
19             slow = slow.next;
20             fast = fast.next.next;
21         }
22         return slow;
23     }
24     private ListNode merge(ListNode first, ListNode second) {
25         ListNode dummy = new ListNode(-1);
26         ListNode cur = dummy;
27         while (first != null || second != null) {
28             if (first == null) {
29                 cur.next = second;
30                 break;
31             } else if (second == null) {
32                 cur.next = first;
33                 break;
34             } else {
35                 if (first.val < second.val) {
36                     cur.next = first;
37                     first = first.next;
38                 } else {
39                     cur.next = second;
40                     second = second.next;
41                 }
42             }
43             cur = cur.next;
44         }
45         return dummy.next;
46     }
47 }