Insertion In Circular Linked List

Easy
0/40
Average time to solve is 12m
profile
Contributed by
13 upvotes
Asked in companies
MicrosoftSOTI

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:



Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
4 0 5
1 2 3 4


Sample Output 1:
5 1 2 3 4


Explanation Of Sample Input 1 :
In this case, ‘k’ = 0 denotes the starting index of the list, so the new element is inserted before the head of the list and the new head will be then a node with ‘data’ = 5.

Hence, the resulting circular linked list would be : 5 1 2 3 4


Sample Input 2 :
3 2 4
10 11 5


Sample Output 2 :
10 11 4 5


Expected Time Complexity:
Try to do this in O(k).


Constraints :
1 <= n <= 10^4
0 <= k <= n
1 <= val <= 10^5
1 <= Node.data <= 10^5

Time Limit: 1 sec
Hint

Can you try iterating over the list?

Approaches (1)
Naive 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’.
Time Complexity

O(K), Where ‘K’ is the position of the nodes to be inserted in the list.

As we are iterating the list for ‘K’ iterations, the time complexity will be O(K)

Space Complexity

O(1).


As we are using the extra pointers ‘ITR’ and ‘temp’ of size ‘4 bytes’, the space complexity will be O(1).

Code Solution
(100% EXP penalty)
Insertion In Circular Linked List
Full screen
Console