147. Insertion Sort List
1. Description
Sort a linked list using insertion sort.
2. Example
Example 1
Input: 4->2->1->3
Output: 1->2->3->4
Example 2
Input: -1->5->3->4->0
Output: -1->0->3->4->5
Example 3
Input: nums = [0]
Output: [0]
Example 4
Input: nums = [1]
Output: [1]
3. Solutions
Linked List
n is number of i_head’s nodes
Time complexity : O($n^2$)
Space complexity : O(1)
/**
* 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)
ListNode* insertionSortList(ListNode* i_head)
{
auto result = new ListNode();
for(auto lastOrderedNode = i_head; lastOrderedNode != nullptr; )
{
for(auto iter = result; ; iter = iter->next)
{
if(iter->next == nullptr || lastOrderedNode->val <= iter->next->val)
{
auto node = lastOrderedNode;
lastOrderedNode = lastOrderedNode->next;
node->next = iter->next;
iter->next = node;
break;
}
}
}
return result->next;
}
};