首页 > 代码库 > 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 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。