sort-list（归并排序和插入排序使得链表有序）

题目描述

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

归并排序算法：时间复杂度是O(logn)，对于数组，空间复杂度是O（n）,对于链表空间复杂度是O（1）

链表的归并排序：

（1）根据快慢指针知道中间的指针

（2）把链表从中间位置的指针断开

（3）递归调用，不喝合并两个有序的两部分链表

/**
 * 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 mid=getMid(head);
        ListNode midnext=mid.next;
    	mid.next=null;//断开
        return MergeList(sortList(head),sortList(midnext));
    }

	private ListNode MergeList(ListNode left, ListNode right) {
		if(left==null) return right;
		if(right==null) return left;
		ListNode head=null;//临时链表保存合并以后的链表
		if(left.val<right.val){
			head=left;
			left=left.next;
		}else{
			head=right;
			right=right.next;
		}
		ListNode temp=head;
		while(left!=null && right!=null){
			if(left.val<right.val){
				temp.next=left;
				left=left.next;
			}else{
				temp.next=right;
				right=right.next;
			}
			temp=temp.next;
		}
		if(right!=null){
			temp.next=right;
		}
		if(left!=null){
			temp.next=left;
		}
		return head;
	}

	private ListNode getMid(ListNode head) {
		ListNode low=head;
		ListNode fast=head;
		while(fast.next!=null&&fast.next.next!=null){
			low=low.next;
			fast=fast.next.next;
		}
		return low;
	}

}

题目描述

Sort a linked list using insertion sort.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
	public ListNode insertionSortList(ListNode head) {
		ListNode dumy=new ListNode(Integer.MIN_VALUE);
		ListNode pre=dumy;
		ListNode cur=head;
		
		while(cur!=null){
			ListNode next=cur.next;//保存当前待插入节点的下一个节点
			pre=dumy;
			while(pre.next!=null&&pre.next.val<cur.val){
				pre=pre.next;//前插法，从新的链表从前到后找当前节点的位置
			}
			//循环出来以后找到当前节点的正确位置就是pre目前的位置
			//插入当前节点
			cur.next=pre.next;
			pre.next=cur;
			//出来下一个节点
			cur=next;
		}
		return dumy.next;
	}
}