首页 > 代码库 > leetcode. Insertion Sort List
leetcode. Insertion Sort List
Sort a linked list using insertion sort.
链表的插入排序，算法可参看数组插入排序，不同之处在于查找插入点时，链表要从前往后查找。
代码如下：
1 ListNode *insertionSortList(ListNode *head) 2 { 3 ListNode *dummy = new ListNode(INT_MIN), *p, *q, *r; 4 ListNode *new_head; 5 dummy->next = head; 6 7 p = dummy->next; 8 while (p != NULL) 9 {10 q = p->next;11 if (q == NULL)12 break;13 for (r = dummy; r->next != q; r = r->next)14 {15 if (q->val <= r->next->val)16 break;17 }18 if (r->next == q)19 {20 p = p->next;21 continue;22 }23 p->next = q->next;24 q->next = r->next;25 r->next = q;26 }27 28 new_head = dummy->next;29 delete dummy;30 return new_head;31 }
注意点：
1、使用dummy节点以方便操作
2、当q需要插入到p之前的节点时，p已经指向下一个节点，不需要再使用p = p->next
leetcode. Insertion Sort List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。