Difficulty: Medium, Asked-In: Microsoft, Google
Key takeaway: An excellent problem to iterative problem solving in a linked list.
We have given the head of a singly linked list, write a program to sort the list using insertion sort, and return the head of the sorted linked list.
Input: [6] -> [2] -> [7] -> [4] ->NULL
Output: [2] -> [4] -> [6] -> [7] ->NULL
Input: [3] -> [-4] -> [-3] -> [1] -> [0] -> NULL
Output: [-4] -> [-3] -> [0] -> [1] -> [3] -> NULL
To understand the implementation, we need to revise the idea of insertion sort on array.
Insertion sort adds one input to the sorted output at each step of iteration and grows partially sorted array size by 1. In other words: At each iteration, insertion sort removes one element from the input data and finds its location in the partially sorted array. This process repeats until no input elements remain.
At any ith iteration of the insertion sort, it divides the array into three parts: current element(A[i]), partially sorted part(A[0…i — 1]), and unsorted part (A[i+1…n-1]). So at each iteration, insertion sort picks the first element from the unsorted part, find position of that element within the sorted part, and insert it there.
We can use the same idea to implement a linked list insertion sort. But there are some key differences:
We start from the unsorted linked list and run a loop to pick each node. To insert the current node in sorted output, we can use a helper function sortedInsert().
This function accepts the head of the partially sorted list and a current node as an argument. Inside the function, we iterates through the start of the list until it finds an element greater than current node. Finally, it return the head of partially sorted linked list.
At each iteration of above loop, we add one node to the correct position in the partially sorted list. In other words, partially sorted list size will grow by 1 at each iteration.
ListNode insertionSortLinkedList(ListNode head)
{
ListNode curr = head
ListNode sortedHead = NULL
while (curr != NULL)
{
ListNode currNext = curr->next
sortedHead = sortedInsert(sortedHead, curr)
curr = currNext
}
return sortedHead
}
All the nodes before curr node are sorted and our goal is to insert curr node in the partially sorted list. So we start from the head and compare each node data with data stored in curr node.
When this function get called for the first node (sortedHead == NULL) or head data is greater than curr node data (sortedHead->data >= curr->data), we insert curr node to the front and return curr pointer as an output.
if(sortedHead == NULL || sortedHead->data >= curr->data)
{
curr->next = sortedHead
return curr
}
Otherwise, we run a loop to skip all the nodes less than curr->data.
ListNode temp = sortedHead
while(temp->next != NULL && temp->next->data < curr->data)
temp = temp->next
By the end of above loop, temp pointer is at the node which is just less than the curr->data. In the worst case, temp may reach to the last node. Whatever be the situation, we need to insert curr node to the next of temp.
curr->next = temp->next
temp->next = curr
Pseudocode implementation of sortedInsert()
ListNode sortedInsert(ListNode sortedHead, ListNode curr)
{
// Insertion at the first position
if(sortedHead == NULL || sortedHead->data >= curr->data)
{
curr->next = sortedHead
return curr
}
else
{
ListNode temp = sortedHead
while(temp->next != NULL && temp->next->data < curr->data)
temp = temp->next
curr->next = temp->next
temp->next = curr
}
return sortedHead
}
In the worst case, we need to traverse complete partially sorted list to insert a node at the correct position. Suppose i number of nodes are sorted and we want to insert (i+1)th node using the helper function. Then total number of comparison operation in the worst case = i. This is a situation of already sorted linked list.
Total count of comparison operation in the worst case = 1 + 2 + 3 + ... + n - 1 = n(n-1)/2 = O(n^2)
The best case situation occur when linked list is reverse sorted, where we need to perform one comparison operation and insert every node at the front of the linked list.
Total count of comparison operation in the best case = 1 + 1 + 1 + ... n times = n = O(n)
As we are using constant number of pointers, space complexity = O(1)
ListNode insertionSortList(ListNode head)
{
if (head == NULL)
return head
ListNode dummy = new ListNode(0)
ListNode currNode = head
ListNode prevNode = dummy
ListNode nextNode = NULL
while (currNode != NULL)
{
nextNode = currNode->next
while (prevNode->next != NULL && prevNode->next->data < currNode->data)
prevNode = prevNode->next
currNode->next = prevNode->next
prevNode->next = currNode
prevNode = dummy
currNode = nextNode
}
return dummy->next
}
Enjoy learning, Enjoy algorithms!