LeetCode :: Insertion Sort List [具体分析]

Sort a linked list using insertion sort.

仍然是一个很简洁的题目，让我们用插入排序给链表排序；这里说到插入排序。能够来回想一下，最主要的入门排序算法。就是插入排序了。时间复杂度为n^2。最主要的插入排序是基于数组实现的。以下给出基于数组实现的插入排序，来体会一个插入排序的思想；

下面仅为数组实现。不是解题代码，没兴趣能够跳过。

void insertionsort (int a[], int N)
{
	for (int i = 1; i < N; i++){
		int tmp = a[i];
		for (int j = i; j >= 0 && a[j] < a[j - 1]; j--)   //这里是升序排列，所以是a[j] < a[j - 1]
			a[j] = a[j - 1];
		a[j] = tmp;
	}
}

当做链表的时候，有两点主要差别：一、因为是单向链表。所以和数组不同的是，每一次都从第一个节点向后扫描。寻找合适的插入位置；当然。数组也是能够这种。

二、数组须要挨个替换。我上面的写法在寻找合适位置的同一时候就直接替换了，所以感觉没那么明显，而链表则是在需找到合适位置之后，把待排序节点拿出插入当中。体现了链表的动态性。

/**
 * 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 == NULL || head->next == NULL)
            return head;
            
        ListNode *tmp = NULL;
        ListNode *pre_tmp = NULL;
        ListNode *dummy = new ListNode(0);
        ListNode *pos = head->next;    //这里用pos指向第一待插入排序数据
        ListNode *pre_pos = head;
        dummy->next = head;
        
        while(pos != NULL){
            tmp = dummy->next;       //这里一開始写成了 tmp = head 一直错，太不细心了。在引入哑节点之后，
                                    //这里就不能等于head,仅仅有这样才干够从第一个開始扫描開始扫描。
            pre_tmp = dummy;
            while(tmp->val < pos->val && tmp != pos){  //第二个条件在数组插入排序时事不用推断的。这里须要注意！
                 pre_tmp = tmp;
                 tmp = tmp->next;
            }    
                
            if (tmp != pos)
            {
             pre_pos->next = pos->next;
             pre_tmp->next = pos;
             pos->next = tmp;
             pos = pre_pos;
            }
            pre_pos = pos;
            pos = pos->next;
        }
        return dummy->next;
    }
};

PS：dummy节点对于头节点可能变化的链表来说，引入是一个非常方便的事情，可是要记得链表的起始用dummy->next表示出，而不是使用head，由于head由于改变节点点，它可能不是头节点 orz