http://oj.leetcode.com/problems/insertion-sort-list/

Insertion Sort List.cpp

typedef ListNode LNode;
class Solution {
public:
	ListNode *insertionSortList(ListNode *head) {
		if (!head) return NULL;
		LNode *newHead=head; LNode *p=head->next;
		newHead->next=NULL;
		while (p) {
			LNode *cur=p; p=p->next;
			newHead=insert(newHead, cur);
		}
		return newHead;
	}
	LNode* insert(LNode *head, LNode *x){
		LNode *pre=NULL; LNode *cur=head;
		while (cur && cur->val < x->val) {
			pre=cur; cur=cur->next;
		}
		if (pre==NULL) {
			x->next=head;
			return x;
		}
		x->next=cur;
		pre->next=x;
		return head;
	}
};