5

Insertion Sort in Linked List

Difficulty: EASY
Contributed By
Sakshi Bansal
Avg. time to solve
10 min
Success Rate
90%

Problem Statement
Suggest Edit

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
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
Reset Code
Full screen
copy-code
Console