148. Sort List

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

Example 1:

1
2
Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2
Input: -1->5->3->4->0
Output: -1->0->3->4->5
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
public class Solution {

    /*
    * 链表合并的递归方式,妙的很,理解上需要从最后一步反推,链表的连接像是倒着连一样
    * */
    public ListNode merge(ListNode h1, ListNode h2) {
        if (h1 == null){
            return h2;
        }

        if (h2 == null){
            return h1;
        }
        if (h1.val<h2.val){
            h1.next = merge(h1.next,h2);
            return h1;
        }
        else{
            h2.next = merge(h1,h2.next);
            return h2;
        }

    }

    /*
    * 同样是递归,原理是归并排序的原理,先分开排序再进行合并,具体原理再多理解一下
    * */
    public ListNode sortList(ListNode head) {
        /*
        * 归并的第一步:确定最后的返回条件
        * */
        if (head == null){
            return head;
        }
        if (head.next == null){
            return head;
        }

        /*
        * 快慢指针达到二分的效果
        * */
        ListNode slow = head, fast = head, pre = head;//pre存储slow指针的上一个节点,用于分割

        /*
        * 由于有快指针,循环条件要以快的那个为准,而且要有两种情况,以防跳到null
        * */
        while (fast != null && fast.next != null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        /*
        * x.next进行分割;不同于slow = slow.next是指针滑动
        * */
        pre.next = null;
        /*
        * 归并的一般推演逻辑
        * */
        ListNode h1 = sortList(head);
        ListNode h2 = sortList(slow);
        return merge(h1,h2);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode.print(solution.sortList(ListNode.createTestData("[2,1,3,5]")));
    }
}

链表排序题: - 用到的排序原理是归并 - 不知道为啥不用其他排序算法 - 各种排序算法优劣学习