leetcode: Sort List

问题描述：

Sort a linked list using insertion sort.

原问题链接：https://leetcode.com/problems/sort-list/

 

问题分析

　　有时候，往往是一些看似简单的问题描述 ，其解决方法越麻烦。这里问题描述确实简单，对于一个链表来说，我们需要寻找一种时间复杂度为O(NlogN)的排序法。对于数组来说，要找到这种时间复杂度的方法有好几种，比如说归并排序，快速排序，堆排序等。这些都是建立在基于数组的索引访问很方便的基础之上的。

　　可是对于链表来说，这又是一个要命的问题。它最方便的访问法就是只能从头往后一个个的访问下去。如果要访问到其中的某个索引位置则相对慢很多。看来我们需要从上述的几种方法中找一种对于索引访问比较少，这样使得方法的性能没有太大影响的才行。

　　我们可以考虑归并排序，它是递归的将一组元素划分成两个部分，一直到无法继续划分位置。然后在递归返回的时候将相邻的两个部分给合并起来。在这里，我们可以将链表首先划分成两个部分。这里可以采用前面快慢指针的手法。这样就得到了两个链表。

　　然后我们再针对两个链表进行合并。而合并链表的手法在之前的一些方法里也有过讨论，我们就是建立一个临时节点，然后将它们两个链表按照大小往里面加。同时每次也移动新链表里元素的节点。

　　这样，把这两个点解决之后，就好办了。我们可以得到如下的详细代码实现：

 

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode fast = head, slow = head, pre = null;
        while(fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode first = sortList(head);
        ListNode second = sortList(slow);
        return merge(first, second);
    }
    
    private ListNode merge(ListNode first, ListNode second) {
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        while(first != null && second != null) {
            if(first.val < second.val) {
                pre.next = first;
                first = first.next;
            } else {
                pre.next = second;
                second = second.next;
            }
            pre = pre.next;
        }
        if(first != null) pre.next = first;
        if(second != null) pre.next = second;
        return dummy.next;
    }
}