[LeetCode] Insertion Sort List

Insertion Sort List

Sort a linked list using insertion sort.

解题思路：

类似于插入排序法。与数组的插入排序法不同的是，链表的插入排序扫描顺序是从左往右扫描，找到第一个大于指定元素的节点N，然后将之插在N节点前面。

今天状态非常不好，这个题目都NG了好几遍。。。

/**
 * 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* myHead = new ListNode(0);
        ListNode* p = head;
        while(p!=NULL){
            ListNode* q = myHead;
            while(q->next != NULL && q->next->val < p->val){
                q = q->next;
            }
            ListNode* r = p->next;
            p->next=q->next;
            q->next=p;
            p=r;
        }
        p = myHead;
        myHead=myHead->next;
        delete p;
        return myHead;
    }
};

[LeetCode] Insertion Sort List

原文：http://blog.csdn.net/kangrydotnet/article/details/46125659