LeetCode 148. Sort List

原题链接在这里：https://leetcode.com/problems/sort-list/

题目：

Sort a linked list in O(n log n) time using constant space complexity.

题解：

divide and conquer. 从中点开始把原list段成两个list. 一直拆到只有一个点，再按照Merge Two Sorted Lists给合并回来。

与Insertion Sort List类似。

Time Complexity: O(nlogn). Space: O(logn), 用了logn层stack.

AC Java:

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public ListNode sortList(ListNode head) {
11         if(head == null || head.next == null){
12             return head;
13         }
14         ListNode mid = findMiddle(head); //找到中点
15         ListNode secondHead = mid.next; //中点后一个点最为另一个head.
16         mid.next = null;    //断开
17         return mergeTwoSortedLists(sortList(head), sortList(secondHead)); //divide and conquer 的merge sort
18     }
19     private ListNode findMiddle(ListNode head){
20         ListNode walker = head;
21         ListNode runner = head;
22         while(runner.next != null && runner.next.next != null){
23             walker = walker.next;
24             runner = runner.next.next;
25         }
26         return walker;
27     }
28     private ListNode mergeTwoSortedLists(ListNode l1, ListNode l2){
29         if(l1 == null){
30             return l2;
31         }
32         if(l2 == null){
33             return l1;
34         }
35         ListNode dummy = new ListNode(0);
36         ListNode cur = dummy;
37         while(l1 != null && l2 != null){
38             if(l1.val <= l2.val){
39                 cur.next = l1;
40                 cur = cur.next;
41                 l1 = l1.next;
42             }else{
43                 cur.next = l2;
44                 cur = cur.next;
45                 l2 = l2.next;
46             }
47         }
48         if(l1 != null){
49             cur.next = l1;
50         }
51         if(l2 != null){
52             cur.next = l2;
53         }
54         return dummy.next;
55     }
56 }