147. Insertion Sort List

1.問題

• 用Insertion sort對linked list排序

2.想法

• 提問

• function header, parameter

• test input

• 觀察

• 說明想法

  • 碰到需要一面前進, 一面從頭找適當位置情形, 通常需要一個dummy node (p)

  • 分成兩段list: p (sort過的list), sort中的list

  • sort中的list: curr指向head後, 讓head = head->next, 因為curr將會移到p list

  • sort過的list:

    • 將p移動到適當的位置: 當p->next->val > curr->val時停下來, 將curr插入p, p->next之間

• 測試計算複雜度

3.程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (!head) {
            return NULL;
        }
        
        ListNode* newNode = new ListNode(0);
        while (head) {
            ListNode* curr = head;
            head = head->next;
            //回到原點
            ListNode* pre = newNode;
            //移動pre到適當位置: 盡可能移動到小於curr的, list的最右端
            while (pre->next && pre->next->val <= curr->val) {
                pre = pre->next;
            }
            curr->next = pre->next;
            pre->next = curr;
        }
        
        head = newNode->next;
        delete newNode;
        return head;
    }
}