 New update is available. Click here to update.

# Insertion Sort in Linked List

Last Updated: 12 Jan, 2021
Difficulty: Easy

## PROBLEM STATEMENT

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