Insertion Sort List - Leetcode Solution

Problem Statement:

Sort a linked list using insertion sort.

Algorithm:

1. Create a dummy node and set its next pointer to head node of the list.
2. Traverse through the list using a current pointer.
3. For each node, compare its value with the value of the previous node. a. If the value of the current node is greater than or equal to the value of its previous node, move the current pointer to the next node. b. Otherwise, find the correct position of the current node by traversing the previous nodes until you find a node whose value is less than or equal to the current node. c. Remove the current node from its current position and insert it after the node found in step b.
4. Repeat steps 2 to 3 until you reach the end of the list.
5. Return the sorted linked list.

Code:

class Solution { public: ListNode* insertionSortList(ListNode* head) { if (!head || !head->next) { return head; }

    ListNode* dummyNode = new ListNode(INT_MIN);
    dummyNode->next = head;
    
    ListNode* curr = head->next;
    ListNode* prev = head;
    
    while (curr) {
        if (prev->val <= curr->val) {
            prev = curr;
            curr = curr->next;
        } else {
            ListNode* pos = dummyNode;
            
            while (pos->next->val <= curr->val) {
                pos = pos->next;
            }
            
            prev->next = curr->next;
            curr->next = pos->next;
            pos->next = curr;
            
            curr = prev->next;
        }
    }
    
    return dummyNode->next;
}

};

Time Complexity: O(n^2) Space Complexity: O(1)

Explanation:

We start with a dummy node, then traverse the list using two pointers, prev and curr. Each time we compare the value of curr and prev, and if curr is smaller than prev, we find the correct position of curr by traversing the previous nodes until we find a node whose value is less than or equal to curr. We then remove curr from its current position and insert it after the node found in the previous step.

We repeat steps 2 to 3 until we reach the end of the list. Finally, we return the sorted list. The time complexity of this algorithm is O(n^2), and the space complexity is O(1).

1