leetcode Insertion Sort List

表示我觉得题目给的接口有点问题，还是我自己理解有问题。如果链表没有头节点，那么必须是传指针的引用啊！

下面贴代码：

#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include "ListNode.cpp"

using namespace std;

class Solution {
public:
    ListNode *insertionSortList(ListNode*& head) {
        if (!head || !head->next){
        	return head;
        }
        
        ListNode* begin = head;
        ListNode* pre = begin;
        ListNode* cur = pre->next;
        
        begin->next = NULL;
        
        ListNode* tmp = begin;
    	
    	while (cur){
    		pre = begin;
    		tmp = begin;
	    	while (tmp){
	    		if (tmp->val > cur->val){
	    			break;
	    		}
	    		
	    		pre = tmp;
	    		tmp = tmp->next;
	    	}
	    	
		    ListNode* toInsert = cur;
			cur = cur->next;
			
	    	if (!tmp){
	    		pre->next = toInsert;
	    		pre->next->next = NULL;
	    	}
			else{
				if (pre == tmp){
					toInsert->next = tmp;
					begin = toInsert;
	    		}
	    		else{
	    			pre->next = toInsert;
					toInsert->next = tmp;	
	    		}
			}
    	}
    	
    	head = begin;
    }
};

int main(){
	ListNode* head = NULL;
	insert(head, 2);
	insert(head, 1);
	//insert(head, -1);
	Solution s;
	s.insertionSortList(head);
	print(head);
}

但需要注意的是链表节点的截断，不过都比较基础，相信稍微想想大家都做得出来！

leetcode Insertion Sort List,布布扣,bubuko.com

leetcode Insertion Sort List

原文：http://blog.csdn.net/boyxiaolong/article/details/21885331