链表归并排序

选择排序超时了，归并排序没超时 =。=

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if(head == null || head.next == null) return head;
        ListNode p = head;
        int len = 0;
        while(p != null) {
            p = p.next;
            len++;
        }
        ListNode faker = new ListNode(0);
        faker.next = head;
        for(int step = 1;step<len;step *= 2) {
            ListNode unsortedHead = faker.next;
            ListNode sortedTail = faker;
            while(unsortedHead != null) {
                ListNode cutHead1 = unsortedHead;
                // 每次切出两段进行归并
                ListNode cutHead2 = split(unsortedHead, step);
                // unsortedHead为切除两段后剩余部分的头指针
                unsortedHead = split(cutHead2, step);
                // 归并后的头指针接到 sortedTail 后面
                sortedTail.next = merge(cutHead1, cutHead2);
                // 将 sortedTail 移到它的尾部
                while(sortedTail.next != null) {
                    sortedTail = sortedTail.next;
                }
            }
        }
        return faker.next;
    }

    ListNode merge(ListNode h1, ListNode h2) {
        ListNode dummy = new ListNode(0), head = dummy;
        while(h1 != null && h2 != null) {
            if(h1.val <= h2.val) {
                head.next = h1;
                h1 = h1.next;
            } else {
                head.next = h2;
                h2 = h2.next;
            }
            head = head.next;
        }
        head.next = h1 == null ? h2 : h1;
        return dummy.next;
    }

    ListNode split(ListNode head, int n) {
        if(head == null) return null;
        ListNode p = head;
        int count = 0;
        while(p != null && --n > 0) {
            p = p.next;
        }
        if(p == null) return null;
        ListNode remain = p.next;
        p.next = null;
        return remain;
    }
}