Sort a linked list using Insertion Sort

Sort a linked list using insertion sort

Difficulty: Medium

Asked in: Microsoft, Google

Understanding the Problem

Problem Description: Sort a linked list using insertion sort and return its head.

Example 1
Input: 8->0->1->3
Output: 0->1->3->8

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

Possible follow-up questions to ask the interviewer :

Are there any repeating elements in the linked list? (Ans: Yes)

The node structure for the Linked List passed to your function will be

class Node
{
    int val
    Node next
    Node(int v)
    {
        val = v
        next = NULL
    }
}

Solution Approach

Let us first understand the flow of insertion sort. At any point of time in insertion sort, it divide the array into three parts

Current element
Sorted part
Unsorted part

Everything before the current element is sorted part and everything after the current element is unsorted part.At each iteration we will pick the first element from the unsorted part, we will find the position of that element within the sorted list, and insert it there. It repeats until no element is present in the unsorted part.

To insert, we will use a helper function sortedInsert() which will return the head of the sorted list after insertion. sortedInsert() accepts a list head and a node as an argument and iterates through the list until it finds an element greater than the node.

Solution Steps

Initialize curr = head , curr will store the current element.
Create and initialize a node sorted_head to track the head of the sorted list. Initialize it i.e. sorted_head = NULL
Iterate the list until curr != NULL

Store the next element after the curr in a node, i.e currNext = curr.next .
Insert the curr in the partially sorted part using the sortedInsert function and update head of the sorted list, i.e sorted_head = sortedInsert(sorted_head, curr) .
Set curr = currNext .

4. Return sorted_head

Pseudo Code

Node insertionSortLinkedList(Node head)
{
    Node curr = head
    Node sorted_head = NULL
    while (curr != NULL)
    {
        Node currNext = curr.next
        sorted_head = sortedInsert(sorted_head,curr)
        curr = currNext
    }
    return sorted_head
}

Node sortedInsert(Node sorted_head, Node new_node)
{
    // Insertion at first position
    if(sorted_head == NULL or head.data >= new_node.data)
    {
        new_node.next = sorted_head
        return new_node 
    }
    else
    {
        Node curr = sorted_head
        while(curr.next != NULL and
                        curr.next.data < new_node.data)
            curr = curr.next
        new_node.next = curr.next
        curr.next = new_node
    }
    return sorted_head
}

Complexity Analysis

In the worst case, we could have to traverse the whole partially sorted list to insert a node in the correct position. (Think!)

Time Complexity: (Traversing the list) * (Inserting in Sorted List)

= O(n)*O(n) = O(n²)

Space Complexity = O(1)

Critical ideas to think!

Which is the fastest algorithm for sorting a linked list: Insertion Sort, Merge sort or Quicksort? Implement and Compare the time & space complexities.
What is the best case complexity of the above algorithm? Also, try to find the condition when it achieves its best case?