[leetcode]Sort List

新博文地址：[leetcode]Sort List

 

Sort List

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

 

 题中要求以O(n log n)的时间复杂度完成排序，并且只能开常数个空间。一般而言，满足O(n log n)的条件，第一直觉就是快排和归并，但是鉴于快排要往前迭代，但是题中要求是单链表，因此选择归并排序。

 

至于归并排序的就不多说了，具体的做法是用递归实现

1. 将链表一分为二（找中点方法有二: 1. 计算中间节点的index（list.size/2）2 快慢指针，我很蛋疼的选了2）

2. 分别对两个半截链表排序（递归实现）

3. 将两个排好序的半截链表进行merge

public class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null){
        	return head;
        }
        ListNode pre = head;
        ListNode post = getMid(head);
        pre = sortList(pre);
        post = sortList(post);
        return mergeList(pre,post);
    }
    public ListNode mergeList(ListNode pre,ListNode post){
    	ListNode head = new ListNode(0);
    	ListNode tail = head;
    	while(pre != null || post != null){
    		if(pre == null){
    			tail.next = post;
    			break;
    		}else if(post == null){
    			tail.next = pre;
    			break;
    		}else{
    			if(pre.val < post.val){
    				tail.next = pre;
    				pre = pre.next;
    			}else{
    				tail.next = post;
    				post = post.next;
    			}
    			tail = tail.next;
    		}
    	}
    		return head.next;
    }
    public ListNode getMid(ListNode head){
    	ListNode fast = head;
    	ListNode slow = head;
    	while(fast.next != null && fast.next.next != null ){
    		fast = fast.next.next;
    		slow = slow.next;
    	}
    	ListNode mid = slow.next;
    	slow.next = null;
    	return mid;
    }
}

 归并排序是最基本最重要的算法之一，用了分治法，需要熟练掌握