首页 > 代码库 > Insertion Sort List

Insertion Sort List

Sort a linked list using insertion sort.

思路:若当前元素比head小,插入已排序队列头部;否则,从前往后查找当前元素的插入位置。

 1 ListNode *insertionSortList( ListNode *head ) { 2     if( !head || !head->next ) { return head; } 3     ListNode *curr = head->next; head->next = 0; 4     while( curr ) { 5         ListNode *next = curr->next; 6         if( curr->val <= head->val ) { 7             curr->next = head; 8             head = curr; 9         } else {10             ListNode *prev = head;11             while( prev->next && prev->next->val < curr->val ) { prev = prev->next; }12             curr->next = prev->next;13             prev->next = curr;14         }15         curr = next;16     }17     return head;18 }