本文共 988 字,大约阅读时间需要 3 分钟。
题目很简单 就是把链表拆分成已经排好序的 ,没有排序的 ,从没有排序的中不断的取元素插入到排好序的链表中
class Solution {public: ListNode* insertionSortList(ListNode* head) { if(!head||!head->next) return head; ListNode *sorted=head; ListNode *unsorted=head->next; ListNode *temp; head->next=NULL; while(unsorted) { temp=unsorted; unsorted=unsorted->next; temp->next=NULL; sorted=insertList(sorted,temp); } return sorted; } ListNode* insertList(ListNode *sorted,ListNode *temp) { if(temp->val<=sorted->val) { temp->next = sorted; return temp; } else { ListNode* scan=sorted->next; ListNode* pre=sorted; while(scan!=NULL&&temp->val>=scan->val) { pre=scan; scan=scan->next; } temp->next=pre->next; pre->next=temp; return sorted; } }};
转载地址:http://whked.baihongyu.com/