Sorted Insert for Circular Linked List-Asked in Interviews.

Problem Statement :

Write a program to insert a new value in a sorted Circular Linked List (CLL).

Solution:

Approach:

Allocate memory for the newly inserted node and put data in the newly allocated node. Let the pointer to the new node be new_node. After memory allocation, the following are the three cases that need to be handled:-

1) Linked List is empty:  
a) since new_node is the only node in CLL, make a self loop.
new_node->next = new_node;
b) change the head pointer to point to new node.
*head_ref = new_node;
2) New node is to be inserted just before the head node:
(a) Find out the last node using a loop.
while(current->next != *head_ref)
current = current->next;
(b) Change the next of last node.
current->next = new_node;
(c) Change next of new node to point to head.
new_node->next = *head_ref;
(d) change the head pointer to point to new node.
*head_ref = new_node;
3) New node is to be inserted somewhere after the head:
(a) Locate the node after which new node is to be inserted.
while ( current->next!= *head_ref &&
current->next->data data)
{ current = current->next; }
(b) Make next of new_node as next of the located pointer
new_node->next = current->next;
(c) Change the next of the located pointer
current->next = new_node;

Code:

Time Complexity: O(N)

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.

--

--

--

Upskilling students for tech placements!

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Resources for Learning Java

What does “Cloud” mean in Human language.

Directus 9 CMS + Gridsome

A refresher on reverse engineering Android mobile application

Generalizing Jenkins — Part 1

Argentina: one of the major tech hubs in the world

Zero To Flutter: Efficiency With VSCode

Task 8 , Retrieve the owner info from vehicle number plate in the image

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Placewit

Placewit

Upskilling students for tech placements!

More from Medium

One Mile on the globe Puzzle

Interview preparation -DSA #day1

Meta / Amazon / Google / Microsoft Interview Question: Wildcard Matching Solution | LeetCode-44…

14 Days Study Plan to Crack Algo I