Insertion Sort in Linked List
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.

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

Question

Insertion Sort in Linked List

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.

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

O(1)

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

Time Complexity: O(n^2)Explanation:

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).