LeetCode Insertion Sort List 最新题解

Insertion Sort List

Sort a linked list using insertion sort.

题目很短，注意：画图，解决边界，特殊情况。插入指针的时候要注意保存原来node的next，这个很容易出错。

一定要优先考虑到头指针和尾指针和空指针的情况。

下面给出完整程序了：

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
	ListNode *insertionSortList(ListNode *head) {
		if(!head) return nullptr;
		ListNode *newH = new ListNode(head->val);
		ListNode *headTemp = head->next;

		while (headTemp)
		{			
			insertNode(newH, headTemp);
		}
		return newH;
	}

	ListNode *findListPos(ListNode *(&h), ListNode *(&node))
	{
		ListNode *htemp = h;
		while (htemp->next && htemp->next->val <= node->val)
		{
			htemp = htemp->next;
		}
		return htemp;
	}

	void insertNode(ListNode *(&h),ListNode *(&node))
	{
		if(!node) return;
		if (!h || node->val < h->val)
		{
			//注意：那里都要注意保存->next的值之后再插入
			ListNode *nodeNext = node->next;
			node->next = h;
			h = node;
			node = nodeNext;
			return;
		}
		//注意这里的插入操作，很麻烦，一定要熟悉！！！
		ListNode *htemp = findListPos(h, node);
		ListNode *saveNode = htemp->next;
		ListNode *nodeNext = node->next;
		htemp->next = node;
		node->next = saveNode;
		node = nodeNext;
	}
};

int main()
{
	ListNode t1(3);
	ListNode t2(4);
	ListNode t3(1);
	t1.next = &t2;
	t2.next = &t3;
	ListNode *h = &t1;
	while (h)
	{
		cout<<h->val<<" ";
		h = h->next;
	}
	cout<<endl;
	Solution solu;
	h = &t1;
	h = solu.insertionSortList(h);
	while (h)
	{
		cout<<h->val<<" ";
		h = h->next;
	}
	cout<<endl;

	system("pause");
	return 0;
}

可以由上面的一大坨代码简化成这样：

//2014-2-19 update
	ListNode *insertionSortList(ListNode *head) 
	{
		ListNode dummy(INT_MIN);//dummy.next = head;无需这句
		while (head)
		{
			ListNode *p = &dummy;
			for ( ;p->next && head->val >= p->next->val; p = p->next);
			ListNode *t = head;
			head = head->next;
			t->next = p->next;
			p->next = t;
		}
		return dummy.next;
	}