[leetcode]Insertion Sort List

新博文地址：[leetcode]Insertion Sort List

 

Insertion Sort List

Sort a linked list using insertion sort.

 用插入排序，对一个单链表进行排序。

插入排序就不多讲了，单链表还是数组，道理都是一样的，只不过单链表略微麻烦一点，好在算法比较简单，难度不大。

     public ListNode insertionSortList(ListNode head) {
    	if(head == null || head.next == null){
    		return head;
    	}
    	ListNode hhead = new ListNode(Integer.MIN_VALUE);
    	hhead.next = head;
    	ListNode begin = head.next;
    	head.next = null;
    	while(begin != null){
    		ListNode tem = hhead;
    		while(tem.next != null){
    			if(tem.next.val < begin.val){
    				tem = tem.next;
    			}else{
    				break;
    			}
    		}
    		if(tem.next != begin){
    			ListNode node = begin.next;
    			begin.next = tem.next;
    			tem.next = begin;
    			begin = node;
    		}else{
    			tem.next = begin;
    			begin = begin.next;
    		}
    	}
    	return hhead.next;
    }