leetcode 名单 Insertion Sort List

Insertion Sort List

Total Accepted: 24444 Total Submissions: 96639My Submissions

Sort a linked list using insertion sort.

题意：用插入排序对一个链表排序
思路：
插入排序对当前元素在前面已经排好的元素中找到一个位置把它插入
能够设置一个指向头节点的dummy元素。统一操作
注：链表中的交换节点操作，不能简单地仅仅交换节点里的value。由于value有可能是非常复杂的类，那样要调用拷贝构造函数、赋值函数，比較费时间。
复杂度：时间O(n^2)，空间O(1)

ListNode *insertionSortList(ListNode *head) {
	if(!head) return NULL;
	ListNode dummy(-1);
	dummy.next = head;
	ListNode *cur = head->next;
	head->next = NULL;
	while(cur){
		ListNode *cur_next = cur->next;
		ListNode *pos = &dummy;
		while(pos->next != NULL && pos->next->val <= cur->val){
			pos = pos->next;
		}		
		ListNode *tem = pos->next;
		pos->next = cur;
		cur->next = tem;
		cur = cur_next;
	}
	return dummy.next;
}