首页 > 代码库 > LeetCode-Insertion Sort List-链表插入排序-链表操作
LeetCode-Insertion Sort List-链表插入排序-链表操作
https://oj.leetcode.com/problems/insertion-sort-list/
插入排序为假设[0,i)已经为有序数组，下一步从[i,n)找最小的元素交换到i处。用指针模拟这个过程即可。就是操作有些麻烦。
每次[head,p)为已经有序的数组，下次从[p,tail]找出最小的节点r以及其前继节点l。将其插入到lp->p之间。并且注意检测这个节点是否为p这样的边界条件。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ const int INF=2147483647;class Solution {public: ListNode *insertionSortList(ListNode *head) { if (head==NULL) return NULL; ListNode *p=head; ListNode *lp=NULL; ListNode *h=head; while(p!=NULL){ int minv=INF; ListNode *l,*r=p; ListNode *lq=lp; ListNode *q=p; while(q!=NULL){ if (q->val<minv){ minv=q->val; l=lq; r=q; } lq=q; q=q->next; } if (r==p) { lp=p; p=p->next; continue; } if (l!=NULL) l->next=r->next; r->next=p; if (lp==NULL) h=r; else lp->next=r; lp=r; } return h; }};
LeetCode-Insertion Sort List-链表插入排序-链表操作
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。