 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

#### 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
``````   Console