https://leetcode.com/problems/sort-list/description/ Sort a linked list in O(n log n) time using constant space complexity. 找到中点之后的处理，和  是一样的 : 然后把tail 传后面去

ListNode tail = mid.next ; //cut it off mid.next = null ; time: o(nlogn) space: o(n): recursive with n stacks

1 public ListNode sortList(ListNode head) { 2         if (head == null || head.next == null) return head ; 3         //merge sort 4         //find the mid, 5         ListNode mid = getMid(head) ; 6         ListNode tail = mid.next ; 7         //cut it off 8         mid.next = null ; 9         //recursive10         ListNode firstHead = sortList(head) ;11         ListNode secHead = sortList(tail) ;12         //merge: same logic as merge two sorted list13          ListNode newHead = merge(firstHead, secHead);14          return newHead;15     }16 17     private ListNode merge(ListNode firstHead, ListNode secHead) {18         ListNode dummy = new ListNode(0) ;19         ListNode curr = dummy ;20         while (firstHead != null && secHead != null){21             if (firstHead.val