首页 > 代码库 > [Leetcode] insertion sort list 链表插入排序
[Leetcode] insertion sort list 链表插入排序
Sort a linked list using insertion sort.
题意:使用插入排序排链表。
思路:所谓的插入排序法,可以理解为,从原链表中取结点,每次都从新的链表的开头开始遍历比较,在新链表中找到不小于当前节点的位置,然后将当前节点插入进去,依次重复这种过程,时间复杂度为O(n^2)。比较大小时可以采用以结点后缀的形式去比较,这样可以在已排好序的新链表中找到最后一个小于当前值的位置,可以省略一多定义一个指针,这种写法还是很值得思考的。还有就是连接新链表时,先连好后面的,然后再连接前面的。还有值得注意的是,每次比较都是从新链表的开始比较,所以要先定位好最开始的起始点。代码如下:
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode *insertionSortList(ListNode *head) 12 { 13 ListNode *newList=new ListNode(-1); 14 while(head) 15 { 16 ListNode *temp=head->next; 17 ListNode *cur=newList; 18 while(cur->next&&cur->next->val<head->val) 19 cur=cur->next; 20 21 head->next=cur->next; 22 cur->next=head; 23 head=temp; 24 25 } 26 return newList->next; 27 } 28 };
[Leetcode] insertion sort list 链表插入排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。