首页 > 代码库 > 147. Insertion Sort List
147. Insertion Sort List
题目:
Sort a linked list using insertion sort.
思路:
链表的插入排序和数组的插入排序略有不同。以链表4->2->3->1->5为例,为方便操作添加一个头节点-1,此时链表为-1->4->2->3->1->5。基本思路为一次选择前后两个节点,若后节点大于前节点则不断向后循环,若后节点小于前节点则取出后节点,并插入到头节点和前节点之间的位置。
举例说明:
- 头节点为-1,cur为节点4,nextnode为节点2。此时,后节点小于前节点,取出节点2,节点3成为新的nextnode。将节点2插入到-1与4之间,此时链表为:-1->2->4->3->1->5。
- 头节点为-1,cur仍然为节点4,nextnode为节点3。此时,后节点小于前节点,取出节点3,节点1成为新的nextnode。将节点3插入到-1与4之间,此时链表为:-1->2->3->4->1->5。
- 头节点为-1,cur仍然为节点4,nextnode为节点1。此时,后节点小于前节点,取出节点1,节点5成为新的nextnode。将节点1插入到-1与4之间,此时链表为:-1->1->2->3->4->5。
- 头节点为-1,cur仍然为节点4,nextnode为节点5。此时,后节点大于前节点,向后循环,nextnode为NULL,排序完成,退出循环。
代码:
1 class Solution { 2 public: 3 ListNode* insertionSortList(ListNode* head) { 4 if (head == NULL || head->next == NULL) 5 return head; 6 ListNode *newhead = new ListNode(-1); 7 newhead->next = head; 8 ListNode *cur = head; 9 ListNode *nextnode = head->next; 10 while (nextnode != NULL) { 11 if (cur->val <= nextnode->val) { 12 nextnode = nextnode->next; 13 cur = cur->next; 14 } else { 15 ListNode *temp = nextnode; 16 cur->next = nextnode->next; 17 nextnode = nextnode->next; 18 19 ListNode *pre = newhead; 20 ListNode *insert = newhead->next; 21 while (insert->val <= temp->val) { 22 pre = insert; 23 insert = insert->next; 24 } 25 pre->next = temp; 26 temp->next = insert; 27 } 28 } 29 return newhead->next; 30 } 31 };
147. Insertion Sort List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。