首页 > 代码库 > 【leetcode】Insertion Sort List （middle）
【leetcode】Insertion Sort List （middle）
Sort a linked list using insertion sort.
思路：
用插入排序对链表排序。插入排序是指每次在一个排好序的链表中插入一个新的值。
注意：把排好序的部分和未排序的部分完全分开，指针不要有交叉。 即不会通过->next 重叠
class Solution {public: ListNode *insertionSortList(ListNode *head) { if(head == NULL) return NULL; ListNode * ans = head; head = head->next; ans->next = NULL; //排好序的第一个结点，后面跟的要是NULL 排好序的部分和未排好序的部分不能重合 while(head != NULL) //还有要插入的 每次都把剩下还未排序部分的头结点插入 { ListNode * pans = ans; //记录插入的位置 ListNode * tmp = NULL; //交换时用的临时的值 if(pans->val >= head->val) //新来的结点最小，是新的头结点 { tmp = head; head = head->next; tmp->next = pans; ans = tmp; continue; } //找到要插入的前一个指针 while(!(pans->val < head->val && (pans->next == NULL || pans->next->val >= head->val))) //比当前结点大，且小于等于后面的结点值，或后面的结点值为0 { pans = pans->next; } tmp = head; head = head->next; tmp->next = pans->next; pans->next = tmp; } return ans; }};
【leetcode】Insertion Sort List （middle）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。