[LeetCode][Medium] 147. Insertion Sort List

Leetcode 網址: https://leetcode.com/problems/insertion-sort-list/

題目說明:

給定一個 Linked List，請使用 Insertion Sort 將這個 List 由小到大排序。

Example 1:
Input: 4->2->1->3
Output: 1->2->3->4

程式碼

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        auto dummyHead = new ListNode(INT_MIN, head);
        
        auto currentNode = dummyHead->next;
        while (currentNode != NULL) {
            auto nextNode = currentNode->next;
            for (auto n = dummyHead; n->next != currentNode; n = n->next) {
                auto tempNode = n->next;
                if (currentNode->val < tempNode->val) {
                    n->next = currentNode;
                    currentNode->next = tempNode;
                    
                    for (n = currentNode; n->next != currentNode; n = n->next);
                    n->next = nextNode;
                    break;
                }
            }
            currentNode = nextNode;
        } 
        return dummyHead->next;
    }
};

結果

Runtime: 80 ms, faster than 10.87% of C++ online submissions for Insertion Sort List.

Memory Usage: 9.5 MB, less than 99.34% of C++ online submissions for Insertion Sort List.