首页 > 代码库 > leetcode 链表 Insertion Sort List
leetcode 链表 Insertion Sort List
Insertion Sort List
Total Accepted: 24444 Total Submissions: 96639My SubmissionsSort a linked list using insertion sort.
题意:用插入排序对一个链表排序
思路:
插入排序对当前元素在前面已经排好的元素中找到一个位置把它插入
可以设置一个指向头节点的dummy元素,统一操作
注:链表中的交换节点操作,不能简单地只交换节点里的value,因为value有可能是很复杂的类,那样要调用拷贝构造函数、赋值函数,比较费时间。
复杂度:时间O(n^2),空间O(1)
ListNode *insertionSortList(ListNode *head) { if(!head) return NULL; ListNode dummy(-1); dummy.next = head; ListNode *cur = head->next; head->next = NULL; while(cur){ ListNode *cur_next = cur->next; ListNode *pos = &dummy; while(pos->next != NULL && pos->next->val <= cur->val){ pos = pos->next; } ListNode *tem = pos->next; pos->next = cur; cur->next = tem; cur = cur_next; } return dummy.next; }
leetcode 链表 Insertion Sort List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。