首页 > 代码库 > 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