Question

Sort a linked list using insertion sort.

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

Solution

Insertion sort is a simple sorting algorithm that works similarly to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Algorithm of Insertion Sort

To sort an array of size n in ascending order:

1. Iterate from arr[1] to arr[n] over the array.
2. Compare the current element (key) to its predecessor.
3. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Basic Approach

For the most basic approach, the linked list can be first converted to an array and then perform insertion sort in the array and then convert the array back to the linked list. This process will take memory O(N) for array formation and time complexity of O(N^2) because of insertion sorting. However, although this process seems easy, it's more time-consuming.

/**
 * 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:
    void insertionSort(deque<int>& arr){
        // gets the size of the array
        int len = arr.size();
        // for each element in array
        for(int i = 0; i < len; i++){
            // this to_sort_value is the unsorted value in current index.
            int to_sort_value = arr[i];
            // basically check for all the elements behind to_sort_value. 
            // If to_sort_value is smaller than the previous value 
            // then we need to slide the big elements and insert the to_sort_value in correct index;
            int j = i - 1;
            while(j >= 0 && to_sort_value < arr[j]){
                 // slide the element to the right
                 arr[j+1] = arr[j];
                 j--;
            }
            arr[j+1] = to_sort_value;
        }
    }

    ListNode* insertionSortList(ListNode* head) {
        // let's save all the elements of head in an vector
        // sort the vector
        // and put back all the element
        deque<int> results;
        ListNode* iterator = head;
        while(iterator != nullptr){
            results.push_back(iterator->val);
            iterator = iterator->next;
        }

        insertionSort(results);

        iterator = head;
        while(iterator != nullptr){
            iterator->val = results.front(); results.pop_front();
            iterator = iterator->next;
        }
        return head;
    }
};

Better Approach

A better approach would be to sort the linked list without converting it into an array. Let's look at the approach stepwise.

ListNode* insertionSortListBetter(ListNode* head){
    if(head == nullptr) return head;
    ListNode* sorted = nullptr; 
    ListNode* current = head;
    while(current != nullptr){
        ListNode* next = current->next;
        insertionSortLinkedList(sorted,current);
        current = next;
    }
    return sorted;
}

Here this is the main function that helps in insertion sorting the linked list. The head pointer of the linked list is passed as the parameter to the function. if the head is null or the linked list is empty then the function would simply return the head as we don't have to perform anything.

In this approach, we are creating a new linked list of sorted nodes. This is currently set to the null. The function consists of main loop that traverses through each node and passes that node along with the sorted linked list to another function insertionSortLinkedList. This function arranges each node in the sorted linked list.

void insertionSortLinkedList(ListNode* &head, ListNode* node){
    if(head == nullptr || head->val >= node->val){
        node->next = head;
        head = node;
    }
    else {
        ListNode* current = head;
        while(current->next != nullptr && current->next->val < node->val){
            current = current->next;
        }
        node->next = current->next;
        current->next = node;
    }
}

Though this looks confusing, this function can be broken down into pieces and explained. Let's suppose the sorted linked list is empty and we are trying to place the first node in the sorted list or the element we are trying to sort has a value less than the value of the head of the sorted linked list, well then the new node will have to be kept at the beginning of the sorted linked list, so the next of new node is pointed to the head and the node is made the head node.

Now, if the sorted linked list is not empty or the new node to be arranged is bigger than the value of the node pointed by the head then, we are entering the else condition. In this block, we are trying to iterate over the sorted linked list to find the node whose value is greater than the new node and we are stopping right before that node whose value is greater than the new node(node to be arranged). And then we are simply inserting the new node between the current node and the next node.

The complete code is provided below.

/**
 * 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:
    void insertionSortLinkedList(ListNode* &head, ListNode* node){
        if(head == nullptr || head->val >= node->val){
            node->next = head;
            head = node;
        }
        else {
            ListNode* current = head;
            while(current->next != nullptr && current->next->val < node->val){
                current = current->next;
            }
            node->next = current->next;
            current->next = node;
        }
    }
    ListNode* insertionSortList(ListNode* head) {
        if(head == nullptr) return head;
        ListNode* sorted = nullptr; 
        ListNode* current = head;
        while(current != nullptr){
            ListNode* next = current->next;
            insertionSortLinkedList(sorted,current);
            current = next;
        }
        return sorted;
    }
};

This step is more efficient than the basic step. This also has a time complexity of O(N^2). This is a very good problem to practice as it helps us to get both understanding of insertion sort and linked list.

Thank you for reading the blog.