首页 > 代码库 > leetcode:Insert Sort List
leetcode:Insert Sort List
问题描述
对一个单链表进行插入排序,head指向第一个结点。
代码
/** * 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) { if(!head||head->next==NULL) return head; ListNode *pstart=new ListNode(0);//添加一个头指针以方便处理,设所有节点数据大于0 pstart->next=head; ListNode *preCur=head,*cur=head->next; while(cur!=NULL) { ListNode *prePos=pstart,* pos=pstart->next; while(pos->val<cur->val) { prePos=prePos->next;//prePos指向带插入位置的前方 pos=pos->next;//pos指向待插入位置的后方 } if(pos!=cur) { preCur->next=cur->next; cur->next=pos; prePos->next=cur; //preCur不变 cur=preCur->next; } else { preCur=cur; cur=cur->next; } } head=pstart->next; delete pstart; return head; } };
时间复杂度
O(N^2),相对于顺序存储减少移动次数。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。