首页 > 代码库 > leetcode 147. Insertion Sort List
leetcode 147. Insertion Sort List
Sort a linked list using insertion sort.
链表插入排序，和数组插入排序类似，但是不需要移动元素，从前向后比较并插入即可。
内外两层循环，时间复杂度O(n^2)
1、使用dummy节点。 2、为便于插入，pre指针指向外层循环节点
1 ListNode *insertionSortList(ListNode *head) 2 { 3 ListNode *dummy = new ListNode(INT_MIN), *p, *q, *pre; 4 dummy->next = head; 5 6 pre = dummy; 7 q = pre->next; 8 while (q != NULL) 9 {10 p = dummy;11 while (p->next != q)12 {13 if (q->val < p->next->val)14 {15 pre->next = q->next;16 q->next = p->next;17 p->next = q;18 q = pre->next;19 break;20 }21 p = p->next;22 }23 if (p->next == q)24 {25 pre = q;26 q = pre->next;27 }28 }29 p = dummy->next;30 delete dummy;31 return p;32 }
leetcode 147. Insertion Sort List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。