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?
Suggested problems to solve
- Merge Two Sorted Lists
- Merge Sort in an array.
- Merge sort in the linked list.
- Reverse a linked list.
- Bubble Sort in the linked list.
- Detect a loop in the linked list.
May the code be with You!
Enjoy Algorithms!