147 - Insertion Sort List

Insertion Sort List

Sort a linked list using insertion sort.
Hide Tags
Linked List Sort
Hide Similar Problems
(M) Sort List

按照要求插入排序，也就是需要从头查找应该插入的位置，然后插入即可。
插入的时候注意pre 和 插入点（pp）不一定是同一个位置。
第一次做的是80 ms，检查了一下，发现代码里对每个点都从头查了一遍，
但实际上仅仅只有那些比前一个节点（已经排好序的最大的值）小的节点，才需要做查找插入，
加了判断条件以后减少到 24 ms。

/**
* 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 dummy(0);
        dummy.next = head;
        if(head && head->next)
        {
            ListNode* pre = head;
            ListNode* p = head->next;
            while(p)
            {
                if(p->val < pre->val)               //inserting only if necessary
                {
                    ListNode* pp = &dummy;          //locate where to insert
                    while((pp->next->val < p->val)) //pp won't exceed pre, so no valid check
                        pp = pp->next;
   
                    pre->next = p->next;
                    p->next = pp->next;
                    pp->next = p;
                }
                else
                    pre = p;                        //no inserting, keep moving                   
                p = pre->next;
            }
        }
        return dummy.next;
    }
};
24 ms.