algoadvance

Leetcode 147. Insertion Sort List

Problem Statement

Given the head of a singly linked list, return the list after sorting it in ascending order using the insertion sort algorithm.

Clarifying Questions

1. Can the list be empty?
   • Yes, the list can be empty. In such cases, the function should return the head as nullptr.
2. What is the expected size of the list?
   • The list can be large, up to the maximum constraint of the system’s memory.
3. Is the input list guaranteed to be a singly linked list?
   • Yes, the problem specifies a singly linked list.
4. Do we need to handle duplicate values in the sorting?
   • Yes, we should correctly place duplicate values in the sorted order.
5. Are there any constraints on memory usage or should we use in-place sorting?
   • Typically, the intention is to perform the sorting in-place to keep additional memory usage minimal.

Strategy

1. Initialization:
   • Create a dummy node to handle edge cases more easily (e.g., inserting at the head).
2. Traversal:
   • Use a pointer to traverse the original list.
3. Insertion Sort:
   • For each node in the original list, find the correct position in the sorted part of the list (initially empty).
4. Insert Node:
   • Insert the node into the correct position. Adjust pointers accordingly.
5. Move to the Next node:
   • Advance to the next node in the original list and repeat until the list is fully sorted.

Code

Here is the code implementation in C++:

/**
 * 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) {
        if (!head || !head->next) return head;
        
        // Create a dummy node to serve as the new head of the sorted list.
        ListNode* dummy = new ListNode(INT_MIN);
        dummy->next = head;
        ListNode* curr = head;
        
        // While there are nodes left in the original list
        while (curr && curr->next) {
            if (curr->val <= curr->next->val) {
                curr = curr->next; // Already in order; move to next element
            } else {
                // Extract the node to be repositioned
                ListNode* toInsert = curr->next;
                curr->next = curr->next->next;
                
                // Find the position to insert the node in the sorted part of the list
                ListNode* prev = dummy;
                while (prev->next->val < toInsert->val) {
                    prev = prev->next;
                }
                
                // Insert the node into the sorted part
                toInsert->next = prev->next;
                prev->next = toInsert;
            }
        }
        
        // Return the sorted list starting from the node next to the dummy.
        return dummy->next;
    }
};

Time Complexity

• Best case: O(n) - If the list is already sorted, we only traverse it once.

• Average and Worst case: O(n^2) - For each node, we traverse a part of the list to find the correct insertion place.

• Space Complexity: O(1) - The sorting is done in-place, so no additional memory besides a few pointers is used.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?