[LeetCode]Insertion Sort List

对于Array来讲，每次insert sort到index i的时候就一直和前面相邻的元素比较，看是否需要交换。LinkedList要模仿insertion sort的话需要解决一个问题，就是在当前节点是没办法和前一个节点比较的，因为单向链表的话只能从头结点开始向后遍历。但是这也给我们提供了另外一个思路，就是我们可以从头开始遍历当前元素应该插入的位置，对于每一个节点，如果其大于等于左边已经sorted部分的最大值，我们直接跳过即可因为不需要变动。对于小于左边已经sorted部分的最大值的节点，我们从head开始寻找其应该插入的部分，插入即可。时间复杂度O(N^2)，就还是insertion sort的时间复杂度，常数空间。代码如下：

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	class Solution {
	public:
	ListNode* insertionSortList(ListNode* head) {
	if(!head || !head->next)return head;
	ListNode* helper = new ListNode(-1);
	helper->next = head;
	auto curr = head;
	while(curr->next)
	{
	if(curr->next->val < curr->val)
	{
	//find insert position
	auto pre = helper;
	while(pre->next->val < curr->next->val)
	pre = pre->next;
	//remove curr->next;
	auto tmp = curr->next;
	curr->next = curr->next->next;
	//insert tmp
	auto next = pre->next;
	pre->next = tmp;
	tmp->next = next;
	}
	else
	curr = curr->next;
	}
	return helper->next;
	}
	};

view raw Insertion Sort List.cpp hosted with ❤ by GitHub