Last Updated: 21 Apr, 2022

Insertion In Circular Linked List

Easy

Asked in companies

Solve now

Problem statement

You are given a circular singly linked list, where every node in the linked list contains a pointer 'next' which points to the next node in the list, and the last node points to the head of the list.

All nodes have some positive integer value 'data' associated with them.

Your task is to insert a new node with 'data' equal to 'val' in the linked list at a given position 'k'.

Note:

The position given will always be less than or equal to the length of the linked list. Assume all the indexing starts from '0'.

Example:

Input : 'k' = 1, 'val' = 5, 'list' = [1, 2, 3, 4]

Output: 1 5 2 3 4

Explanation:
The node with 'data' = 5, is inserted at position 1(0 indexed) in the circular linked list as follows:

Input Format :

The first line of input contains three integers 'n', ‘k’, and 'val', denoting the length of the linked list, the position of insertion operation, and the value of 'data' of new node to be inserted in the list respectively.

The second line of input contains an array of positive integers denoting the nodes of the linked list.

The last element of the list always points to the first element in the list in order for the list to be a circular linked list.

Output format :

Print the circular linked list after the insertion operation.

Note :

You don't need to print anything. It has already been taken care of. Just implement the given function.

Return the head of the modified linked list. Your returned linked list will be validated to check if it's a circular linked list and it's data printed. If your returned linked list is not a circular linked list, '-1' will be printed.

Solve now

Approaches

01 Approach

Approach:

Iterate the list starting from the head to the ‘Kth’ node.

Insert a new node ‘TEMP’ which is pointing to the ‘Kth’ node next and then change the ‘Kth’ node next to ‘TEMP’. Like:

Algorithm :

Find length of the list and store it in the variable ‘LEN’
Firstly check if the new node is inserted at the beginning as this is a special case that is to be handled separately:
- Set the ‘K’ to length of list, as whether a node is inserted at the beginning or the end of the circular linked list doesnt matter, but take special care while printing the list.
Create an iterator ‘ITR’ pointing to ‘HEAD’ initially to travel the list.
For I from ‘0’ to ‘K-1’:
- Make the ‘ITR’ point to ‘Next’ of ‘ITR’.
Create a ‘TEMP’ Node pointer of value ‘VAL’
To insert the ‘TEMP’ at the ‘Kth’ position do the following:
- Assign ‘TEMP->next’ as ‘ITR->next’.
- Then assign ‘ITR-> next’ as ‘TEMP’
- This inserts the ‘TEMP’ pointer at the ‘Kth’ position in the list.
Return ‘HEAD’ if the node is not inserted at the beginning of list, else ‘TEMP’.

Solve now