Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Insertion Sort in Linked List

Easy

0/40

Average time to solve is 10m

Contributed by

20 upvotes

Asked in companies

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 1

Try to use pointers for manipulating the given list.

Approaches (1)

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

(100% EXP penalty)

Insertion Sort in Linked List

Interview problems

c++

Node *insertionSortLL(Node *head) {

if (head == nullptr || head->next == nullptr)

return head;

Node *st = head;

Node *temp = st->next;

while (temp != nullptr) {

if (temp->data >= st->data) {

st = temp;

temp = temp->next;

} else {

st->next = temp->next;

Node *prev = nullptr;

Node *curr = head;

while (curr != st && curr->data <= temp->data) {

prev = curr;

curr = curr->next;

}

if (prev == nullptr) {

temp->next = head;

head = temp;

} else {

temp->next = curr;

prev->next = temp;

}

temp = st->next;

}

return head;

}

62 views

0 replies

0 upvotes

Prakash Pramanik

Interview problems

Insertion Sort in Linked List

class Node:

def __init__(self, data):

self.data = data

self.next = None

def countLL(head1):

c=0

l=[]

temp=head1

while temp!=None:

c+=1

l.append(temp.data)

temp=temp.next

l.sort()

return l

def insertionSortLL(head):

x=countLL(head)

dummy=Node(-1)

temp=dummy

for i in range(len(x)):

temp.next=Node(x[i])

temp=temp.next

return dummy.next

37 views

0 replies

0 upvotes

IIT

Interview problems

Java Solution in very Easy Way with the reference of insertion of node in sorted list

public class Solution
{
public static Node insertionSortLL(Node head)
    {
        // Write your code here
        if(head == null || head.next == null)return head;
        Node st = head;
        Node temp = st.next;
        while(temp != null){
            if(temp.data >= st.data){
                st = temp;
                temp = temp.next;
            }else{
                st.next = temp.next;
                Node prev = null;
                Node curr = head;
                while(curr != st && curr.data <= temp.data){
                    prev = curr;
                    curr = curr.next;
                }
                if(prev == null){
                    temp.next = head;
                    head = temp;
                }else{
                    temp.next = curr;
                    prev.next = temp;
                }
            }
            temp = st.next;
        }
        return head;
    }
}

119 views

0 replies

1 upvote

Sarthak Jain

Interview problems

Java Optimal Solution

public class Solution {

public static Node insertionSortLL(Node head) {

Node dummy = new Node(100000);

while (head != null) {

Node next = head.next;

Node temp = dummy;

while (temp.next != null && temp.next.data < head.data) {

temp = temp.next;

}

head.next = temp.next;

temp.next = head;

head = next;

}

return dummy.next;

}

105 views

0 replies

0 upvotes

Gokul R

Interview problems

Easy Python Approach

def sortedInsert(head, node):
	# checking if head is empty or head's data is greater than
	# node's data
	if head is None or head.data > node.data:
		# "head" is greater than "node" so it is placed next to
		# "node" and "node" is set as the new "head"
		node.next = head
		head = node
	else:
		current = head
		# looped till next node's data is lesser than node's data 
		while current.next and current.next.data < node.data:
			current = current.next
		# now the "current.next" has data greater than node's data
		# so it is placed next to "node"
		node.next = current.next
		# then "node" is placed next to "current" node whose data is
		# greater than "current" node
		current.next = node
	# finally the new "head" is returned
	return head

def insertionSortLL(head):
	# taking empty sorted linked list
	sortedLL = None
	current = head
	# looping till the linked list becomes empty
	while current:
		next = current.next
		# passing sorted linked list and current node and
		# receiving new sorted linked list
		sortedLL = sortedInsert(sortedLL, current)
		current = next
	# finally returning the sorted linked list
	return sortedLL

python

81 views

0 replies

0 upvotes

Abhi shikth

Interview problems

INsertion Sort List

public class Solution

{

public static Node insertionSortLL(Node head)

{

// Write your code here

Node dummy = new Node(0);

while(head != null)

{

Node frwd = head.next;

Node temp = dummy;

while(temp.next != null && temp.next.data < head.data)

{

temp = temp.next;

}

head.next = temp.next;

temp.next = head;

head = frwd;

}

return dummy.next;

}

242 views

0 replies

0 upvotes

Aaditya Surana

Interview problems

Python easy solution to understand

def insertionSortLL(head):
    dummynode=Node(0,head)
    prev=head
    curr=head.next
    while curr:
        if curr.data>=prev.data:
            prev=curr
            curr=curr.next
            continue
        temp=dummynode
        while curr.data>temp.next.data:
            temp=temp.next
        prev.next=curr.next
        curr.next=temp.next
        temp.next=curr
        curr=prev.next
    return dummynode.next

108 views

0 replies

0 upvotes

Codestudio

Interview problems

Discussion thread on Interview Problem | Insertion Sort in Linked List

Hey everyone, creating this thread to discuss the interview problem - Insertion Sort in Linked List.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Insertion Sort in Linked List

376 views

4 replies

0 upvotes

Console