【题目】

Sort a linked list using insertion sort.

【分析】

无

【代码】

/*********************************
*   日期：2015-01-09
*   作者：SJF0115
*   题目: 147.Insertion Sort List
*   来源：https://oj.leetcode.com/problems/insertion-sort-list/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
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 == NULL){
            return NULL;
        }//if
        // 添加头结点
        ListNode *dunny = new ListNode(-1);
        ListNode *p = dunny;
        ListNode *cur = head;
        // cur从第二个元素开始遍历 cur指向第一个未排序元素
        while(cur){
            // cur要跟之前每个元素进行比较，直到找到正确位置
            p = dunny;
            // 比较
            while(p->next != NULL && p->next->val < cur->val){
                p = p->next;
            }//while
            // 记录未排序的第一个元素
            ListNode *nextNode = cur->next;
            // cur放到相应的位置
            cur->next = p->next;
            p->next = cur;
            // 修改cur指针 指向未排序的第一个元素
            cur = nextNode;
        }//while
        return dunny->next;
    }
};

// 创建链表
ListNode* CreateList(int A[],int n){
    ListNode *head = NULL;
    if(n <= 0){
        return head;
    }//if
    head = new ListNode(A[0]);
    ListNode *p1 = head;
    for(int i = 1;i < n;i++){
        ListNode *node = new ListNode(A[i]);
        p1->next = node;
        p1 = node;
    }//for
    return head;
}

int main() {
    Solution solution;
    int A[] = {5,12,3,10,11,8};
    ListNode *list = CreateList(A,6);
    ListNode *head = solution.insertionSortList(list);
    // 输出
    ListNode *p = head;
    while(p){
        cout<<p->val<<" ";
        p = p->next;
    }//while
    cout<<endl;
}