Insertion Sort in Linked List

Easy
0/40
Average time to solve is 10m
profile
Contributed by
20 upvotes
Asked in companies
GooglePaytm (One97 Communications Limited)Disney + Hotstar

Problem statement

You are given an arbitrary linked list consisting of 'N' nodes having integer values. You need to perform insertion sort on the linked list and print the final list in sorted order.

In other words, you are given a singly linked list, you need to perform insertion sort on it.

Insertion Sort is a sorting algorithm that removes one element from the input data, finds the location it belongs within the sorted list and inserts it there. It repeats until no input elements remain.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of the input contains a single integer T, representing the number of test cases. 

The first line of each test case contains space-separated integers denoting the elements of the singly linked list terminated by -1.

Hence, -1 would never be a list element.
Output Format 
For each test case, print space-separated integers denoting the elements of the linked list after performing the insertion sort.

Print the output of each test case in a separate line.
Note 
You do not need to print anything. It has already been taken care of. Just implement the given function. Also, try to sort the linked list in-place.
Constraints 
1 <= T <= 50
1 <= N <= 10^3
0 <= value of node < 10^9

Time Limit: 1sec
Sample Input 1
2
4 2 1 3 -1
19 3 6 1 5 -1
Sample Output 1
1 2 3 4
1 3 5 6 19
Explanation for Sample Input 1
Test Case 1: The given linked list [4 2 1 3] after sorting becomes [1 2 3 4] which is the required output.

Test Case 2: The given linked list is [ 19 3 6 1 5 ]. After sorting list become [ 1 3 5 6 19 ].
Sample Input 2
2
5 3 1 2 4 -1  
5 6 7 -1
Sample Output 2
1 2 3 4 5
5 6 7
Hint

Try to use pointers for manipulating the given list.

Approaches (1)
Try to use pointers for manipulating the given list.

For solving this problem, we will use the fundamental concept of Insertion Sort i.e, to divide the input array into an unsorted and sorted partition. After that, keep placing elements from the unsorted partition into its correct position in the sorted partition.  We will make use of pointers to keep track of various positions in both the lists and modify these pointers only.

 

  • First, create an empty dummy linked list, which will store the final sorted array. (let this be called ‘sorted’).
  • Create a pointer ‘current’ which will be used to iterate over the given SLL. Initially, ‘current’ points to the head of the linked list.
  • Now we will select the elements of the linked list one by one using a while loop and store them at their correct position in the sorted list.
  • As we will be modifying the next pointer of the current node, it is better to store the original next pointer in a temporary variable, so that it is not lost and we can carry out the next iterations.
  • To place a node at its correct position in the sorted list, we use a function called “sortedInsert” which takes the head of the sorted list and the new node to be inserted as parameters.
  • In the “sortedInsert” function, we again make use of pointers to keep track of the position where the element should be inserted and then modify the original links to accommodate the new node.
  • Finally, return the sorted list and terminate.
Time Complexity

O(N^2), where N is the number of nodes in the linked list.

 

As we are calling sorted insert function for every element in the list, the time complexity is O(N^2).

Space Complexity

O(1)

 

As we are only modifying the pointers and not creating any new list.

Code Solution
(100% EXP penalty)
Insertion Sort in Linked List
Full screen
Console