|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 对链表进行插入排序。
- 插入排序的动画演示如上。从第一个元素开始,该链表可以被认为已经部分排序(用黑色表示)。
- 每次迭代时,从输入数据中移除一个元素(用红色表示),并原地将其插入到已排好序的链表中。
-  
- 插入排序算法:
- 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
- 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
- 重复直到所有输入数据插入完为止。
-  
- 示例 1:
- 输入: 4->2->1->3
- 输出: 1->2->3->4
- 示例 2:
- 输入: -1->5->3->4->0
- 输出: -1->0->3->4->5
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/insertion-sort-list
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- class Solution {
- public:
- ListNode* insertionSortList(ListNode* head) {
- ListNode* store = head;
- ListNode* res = new ListNode(INT_MIN);
- ListNode* fix = res;
- while(store != NULL){
- if(store -> val >= res -> val){
- res -> next = new ListNode(store -> val);
- res = res -> next;
- }else{
- ListNode* temp = fix;
- ListNode* temp_pre = new ListNode(-1);
- while(temp -> val < store -> val){
- temp_pre = temp;
- temp = temp -> next;
- }
- temp_pre -> next = new ListNode(store -> val);
- temp_pre = temp_pre -> next;
- temp_pre -> next = temp;
- res = temp;
- while(res -> next != NULL){
- res = res -> next;
- }
- }
- store = store -> next;
- }
- return fix -> next;
- }
- };
复制代码 |
|