147. 對鏈表進(jìn)行插入排序

從第一個(gè)元素開始，該鏈表可以被認(rèn)為已經(jīng)部分排序（用黑色表示）。
每次迭代時(shí)，從輸入數(shù)據(jù)中移除一個(gè)元素（用紅色表示），并原地將其插入到已排好序的鏈表中。

插入排序算法：

插入排序是迭代的，每次只移動(dòng)一個(gè)元素，直到所有元素可以形成一個(gè)有序的輸出列表。
每次迭代中，插入排序只從輸入數(shù)據(jù)中移除一個(gè)待排序的元素，找到它在序列中適當(dāng)?shù)奈恢茫⑵洳迦搿?重復(fù)直到所有輸入數(shù)據(jù)插入完為止。

示例 1：

輸入: 4->2->1->3
輸出: 1->2->3->4

示例 2：

輸入: -1->5->3->4->0
輸出: -1->0->3->4->5

好久沒做鏈表方面的題了，突然想到上一次看頭條面試時(shí)有問到鏈表相關(guān)的知識(shí)，于是想著這幾天復(fù)習(xí)一下這方面的，一開始還真不太會(huì)，看別人的源代碼有些懵.... 但是多看了幾套別人的鏈表插入代碼，就差不多能自己敲出來了，
思路很簡單
因?yàn)殒湵碇械恼麄€(gè)一串?dāng)?shù)都是從小到大排列的，而有序的數(shù)組初始時(shí)只有第一個(gè)數(shù) 所以一開始便劃分為：第一個(gè)數(shù)自成一個(gè)有序體系，剩下的數(shù)是無序體系的數(shù)字，這樣的話只要每一次都從無序數(shù)組中提取出來一個(gè)數(shù)，然后與有序數(shù)組中每個(gè)數(shù)字一一進(jìn)行比較，如果比任何一個(gè)大，那么就插入到該數(shù)之后。如果比他們都小，那么就是另一種情況，得進(jìn)行頭插。
之前返回頭指針即可。
源代碼如下：

/**
 * 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) {
        ListNode * unFirst = NULL;
        ListNode * front = NULL;
        ListNode * inNode= NULL;
        ListNode * cur = NULL;
        cur = head;
        if (head == NULL) {
            return head;
        } else {
        if (head->next != NULL) {
        unFirst = head->next;
        } 
        cur->next = NULL;
        while (unFirst != NULL) {
            cur = head;
            front = unFirst;
            while (cur != NULL && cur->val < front->val) {
                inNode = cur;
                cur = cur->next;
            }
            unFirst = unFirst->next;
            if (cur == head) {
                head = front;
            } else {
                inNode->next = front;//插入前一個(gè)比她小的數(shù)的后面 兩者相鄰
            }
            front->next = cur;
        }
            return head;
        }
    }
};