## Insert into a Cyclic Sorted List

August 12, 2011 in linked list

Given a node from a cyclic linked list which has been sorted, write a function to insert a value into the list such that it remains a cyclic sorted list. The given node can be any single node in the list.

__EDIT:__

Thanks to dear readers **Saurabh** and **reader** who pointed out my mistake. When the list has only one value, inserting a different value would be handled by case 3), ** not** case 1). Besides, I believe I did not explain “What is a cyclic sorted list” nicely, as this had caused some confusion. Imagine you have a sorted list, but its tail points back to its head. In other words, the list must have a minimum node, continue in a non-descending order, and eventually points back to this minimum node itself. And the only way to access the list is via aNode, which can point to any node in the list and

**does not**necessarily point to the minimum node.

First, it is important that you understand what a cyclic linked list is. A cyclic linked list differs from a normal linked list in that its tail node points back to its head node instead of NULL.

This problem seems a little tricky because the given node is not necessarily the list’s head (ie, the node that has the smallest element). It shouldn’t take you too long to come up with an idea, but beware. There are hidden traps around the corner and you are bound to make some mistakes if you are not careful in your thoughts.

A cyclic sorted linked list. Note that the tail is pointing back to its head. The only reference to the list is a given node which can be any node in the list. Let’s say that you need to insert 4 into the list.

This is how the cyclic list becomes after inserting 4. Note that the cyclic linked list remained in sorted order.

**Hints:**

It is best to list all kinds of cases first before you jump into coding. Then, it is much easier to reduce the number of cases your code need to handle by combining some of them into a more generic case. Try to also list down all possible edge cases if you have time. You might discover a bug before you even start coding!

**Solution:**

Basically, you would have a loop that traverse the cyclic sorted list and find the point where you insert the value (Let’s assume the value being inserted called *x*). You would only need to consider the following three cases:

**prev→val ≤***x*≤ current→val:- Insert between prev and current.
*x*is the maximum or minimum value in the list:- Insert before the head. (ie, the head has the smallest value and its prev→val > head→val.

**Traverses back to the starting point:**- Insert before the starting point.

Most people have no problem getting case 1) working, while case 2) is easy to miss or being handled incorrectly. Case 3), on the other hand is more subtle and is not immediately clear what kind of test cases would hit this condition. It seemed that case 1) and 2) should take care of all kinds of cases and case 3) is not needed. Think again… How can you be sure of that? Could you come up with one case where it hits case 3)?

- Q: What if the list has only one value?
- A:
~~Handled by case 1)~~. Handled by case 3). - Q: What if the list is passed in as NULL?
- A: Then handle this special case by creating a new node pointing back to itself and return.
- Q: What if the list contains all duplicates?
- A: Then it has been handled by case 3).

Below is the code. You could combine both negation of case 1) and case 2) in the while loop’s condition, but I prefer to use break statements here to illustrate the above idea clearer.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | void insert(Node *& aNode, int x) { if (!aNode) { aNode = new Node(x); aNode->next = aNode; return; } Node *p = aNode; Node *prev = NULL; do { prev = p; p = p->next; if (x <= p->data && x >= prev->data) break; // For case 1) if ((prev->data > p->data) && (x < p->data || x > prev->data)) break; // For case 2) } while (p != aNode); // when back to starting point, then stop. For case 3) Node *newNode = new Node(x); newNode->next = p; prev->next = newNode; } |

zhanwu said on August 15, 2011

I don’t understand why you need case 3).

In case of all duplicates, x (the value to be inserted) should be inserted right after the starting node, since it satisfies rule 1 immediately.

+11337c0d3r said on August 15, 2011

The problem is you don’t know it has all duplicates until you traverse back to the starting point.

+1zhanwu said on August 17, 2011

say we have a list 1 -> *1 -> 1 -> 1 -> (point back), and our starting point is the second 1 in the list.

if the number to insert is not 1, then it is either a maximum or a minimum of the new list, that’s case 2.

if the number to insert is also 1, then 1 <= 1 <= 1 which means it should be inserted right after the starting point, that's case 1

am I missing anything?

0zhanwu said on August 17, 2011

read it again and figured out your logic

the code is quite clear but the explanation above is rather confusing

01337c0d3r said on August 17, 2011

Thanks for your feedback, zhan.

I agree it is quite confusing.

The second condition:

if ((prev->data > p->data) && (x < p->data || x > prev->data)) break;

doesn’t exactly mean that it breaks when x is the maximum or minimum in the list.

It only breaks when the prev element is greater than the current element (ie, the cyclic point where prev is largest and current is smallest) and x is smallest or largest element in the list if inserted.

Like you said, it can be actually handled in only two cases, like the example you gave. But that would require you to traverse the entire list to find the cyclic point. With the code I gave above, it is more efficient and able to break early in some cases.

0Ratna Kumar said on August 16, 2011

I guess the second case was not handled properly in the code.Say, if I pass the value 0 to the list, it wont break as expected.

01337c0d3r said on August 16, 2011

Using your example, x = 0, prev points to 5 and p points to 1.

if ((prev->data > p->data) && (x < p->data || x > prev->data))

Then it will satisfy the above condition and break for the 2nd case.

+1Ratna Kumar said on August 17, 2011

Yup, it breaks as you said.

I think the head of the linked list should also be changed when we are inserting the new node in the beginning.

3rd case can be in turn split into two types after the break.

Type 1: Insert at the beginning. Code: aNode = newnode;

Type 2: Insert at the end. code. //Do nothing.

+1Ratna Kumar said on August 17, 2011

There’s a typo in the above comment, it’s in the 2nd case

0Ali said on December 29, 2013

Ratna I think you are confusing aNode as head node having the smallest value, but we have not been given a head node instead any node from that list so updating it wont do any good. In the first case setting aNode is just to create a handle to the CSL.

0bread said on August 19, 2011

I don’t think we should make the assumption that the list is ASC sorted.

0Ramesh said on August 22, 2011

You can first find whether list is sorted in ASC or DESC order and then check conditions accordingly.

0bread said on September 5, 2011

of course we can… my point is that we definitely need this

0Jay said on November 12, 2013

Good luck detecting if either of these is asc or desc:

5 (single list)

2->3 (desc list with starting point as second element!)

How the data is structured is outside the scope of this function itself. If you wanted to do this, you’d need your function to take this as an input (eg a function pointer).

0Saurabh said on August 24, 2011

What if the list has only one value?

Handled by case 1).

Isn’t it actually handled by case 3 ? What if i have a List with one value say “4″ and I want to add “3″ or “5″ to the list.

+11337c0d3r said on December 28, 2011

Thanks for pointing out this mistake. Another reader has pointed out below, and I just noticed it. Sorry for not noticing your comment earlier.

0fatalerror said on August 27, 2011

“if ((prev->data > p->data) && (x data || x > prev->data))”

can’t it just be

” if ((prev->data > p->data)) ”

Right half condition serves no purpose in a circular linked list,

am i wrong ?

Thank u.

0Jay said on November 12, 2013

Consider the list:

5 6 7 1 2

Just because 7 is greater than 1 doesn’t mean you’re ready to insert 3. Only the max or min value should be inserted where the tail meets the head, so you need to keep going.

0vinay said on October 23, 2011

This question has taught me to check all the edge cases before we code !! Thanks

0A_Kareem said on November 6, 2011

hi, 1337c0d3r

I am really excited with your great thinking and appreciate your efforts.

I would like to discuss this with you, I think you need to add these two lines to the endof your function to work properly to change the head or list pointer in case of you insert before the head,

if ((x data) && (p == aNode))

{

aNode = newNode;

}

Regards

0A_Kareem said on November 6, 2011

sorry the line is

if ((x data) && (p == aNode))

{

aNode = newNode;

}

0A_Kareem said on November 6, 2011

sorry again

if ((p->data > x ) && (p == aNode))

{

aNode = newNode;

}

0flo said on November 10, 2011

Thanks for the problem, implemented something similar.

I will do all the problems you posted on the site and comment on every one to thank you and remind me I done them

0jr said on November 21, 2011

what about this

void Insert(strcut node** source, int num)

{

struct node* newNode = maclloc(sizeOf(struct node));

newNode->num = num;

if (*souce == NULL || *(source->num) >= num)

{

nwNode->next = *source;

*source = newNode;

}

else

{

struct node* current = *source

while(current->next != NULL && current->next->num > num)

{

current = current->next;

}

newNode->next = current->next;

current->next = newNode;

}

}

0reader said on December 27, 2011

The code posted is wrong.It does not handle the case of a list with 1 node and trying to insert a value less than the one in the existing (only) node of the list. Example: list with just 1 node (pointing to itself) with value

2. Try to insert value1.The code will insert a new node after the existing one breaking the sorted order.01337c0d3r said on December 27, 2011

hi reader,

thanks for your comment and pointing out your concern. Since the cyclic sorted list doesn’t have a head (it is only referred by aNode (which can be any node) in the list).

Therefore, by inserting a smaller value before aNode (any node), it doesn’t break the sorted order per say.

Think of the following list, which is 5->1->3 [3 points back to 5] where aNode is pointing to 5, it doesn’t break the sorted order.

0reader said on December 27, 2011

I see what you mean. But when you would build the cyclic list, inserting the elements in sorted order, the code would have a reference of the first node i.e. the node containing the min value. Wouldn’t this be “treated” in the code as the head of the list?

01337c0d3r said on December 27, 2011

Yes, the smallest value would be the head. For your example with a value of 2, inserting 1 will satisfy the condition prevâ†’val â‰¤ x â‰¤ currentâ†’val: break the loop, and 1′s next will point to 2, and 2′s next point back to 1. This seem correct to me.

Are you suggesting that in this case, we should update the head to point to 1?

0reader said on December 27, 2011

At this point you are incorrect. None of the 2 conditions are satisfied when we try to insert the value

1in a list wich has only one node with value2.Neither the first

nor the second

. So you go out of the

whileloop immediately and the next pointer of prev (which has value 2) now points to a node with value 1 i.e. less than the prev node. Do you agree on this or am I missing something?01337c0d3r said on December 27, 2011

Thanks for your response. When we try to insert the value 1 into one node with value 2, prev and p both point to 2 initially (in the first iteration of do-while loop, note that p->next points to itself, which is 2) and the condition (x < = p->data && x >= prev->data) is satisfied, so it breaks out of the loop.

0Jay said on November 12, 2013

It’s a circular list. There is no “head”. The parameter is passed in as “a node” for this reason.

The initial pointer is not guaranteed to point to the lowest value, just a value. Inserting 1 into the list 2 will always have this effect.

You could take the pointer by reference and change it to point to the newly inserted value if you prefer, but is not required for correctness. (This would have significant performance benefits if you were inserting sorted values.)

0reader said on December 27, 2011

I am sorry but I don’t see what you mean.If x equals 1 and p-data and prev->data are both equal to 2 then how is the condition

satisfied? The second part of the

ifis false. So we exit the while loop and at this point we have prev==p==p->next.Then as a result of the last 3 lines we have:

So the new node with value 1 is inserted after the node with value 2 which is p or prev or aNode

01337c0d3r said on December 28, 2011

Hey reader, I want to thank you for pointing out my mistake. I can’t believe I didn’t notice this condition (x < = p->data && x >= prev->data) is not satisfied when x is 1 and the only data in the list is 2. (p and prev both point to 2).

And you are right about the second condition too (it won’t match). Which comes to the while loop, and this evaluates to be false (since p == aNode, both points to 2), so it breaks out of the while loop.

Up to this point, I agree with you so far. But the last point you are saying 1 -> 2, and 2 -> 1 is not correct. But without doing this it would never satisfy the cyclic property, which says the tail must point back to the head.

Thanks again for pointing out the mistake!

01337c0d3r said on December 28, 2011

I have updated with EDIT on top of the post. Please let me know if this clarify this a little bit, and I appreciate your comments. Thank you!

0reader said on December 28, 2011

Hi 1337c0d3r,

So you are saying that the fact that the code ends up with a list of this form:

2–>1

is irrelevant since the list is cyclic? Did I get your last comment?

But if you agree that in a

sortedcyclic list the head is the smallest element then the caller of the function would end up with a list in descending order.I agree that in general a cyclic list does not have a head, but I think there is a subtlety in the sorted case. Or am I missing your point?

I agree that the the last node must point back to the head, but shouldn’t we end up with

1 –> 2

not with

2 –> 1 ?

0reader said on December 28, 2011

@1337c0d3r

May be I am splitting hair but what I am trying to say is the following:

In a cyclic sorted list with many nodes which node is passed in the method is irrelevant.

But in case of a cyclic sorted list with only one node, the only node that can be passed to the method is the head which we have defined as the node with the minimum element of the list (and assumed that normally the calling code would keep it as a reference).

So the result of the posted code would be

2–>1 as mentioned in my previous comment.

A way to fix this with minimum change in your code is by adding a flag before you

breakout of thewhileloop indicating that you are not in the case of a list with one node. Then take into account if the node should be inserted before prev or not. I.e.Haven’t written C++ in a while so, sorry if I messed up something.

But I am interested on your opinion on this subtlety.

Thanks

0raghavG said on February 27, 2012

the code exact&works for all cases…..

explanation for all cases including while(3rd case):

case1 handles the “duplicate case” and “only one element in the list case” also along with element(given x) in between case.

If either case2 fails or case1 fails (means that there are bigger elements in forward direction from anode->next), then “while(p!=anode)” is needed to progress in the list .i.e 3rd case …

0raghavG said on February 27, 2012

sorry for above explanation….as it is not covering in the case of “single element exist in list and given element(x) is either greater or lesser to that one”..

i think the following code will cover all the cases….

comment:little change to first solution

void insert(Node *& aNode, int x) {

if (!aNode) {

aNode = new Node(x);

aNode->next = aNode;

return;

}

Node *p = aNode;

Node *prev = NULL;

do {

prev = p;

p = p->next;

if (x data && x > prev->data) break;

if (prev->data > p->data)&&(x>prev->data!!xdata) break;

if(prev->data==p->data) break;

} while (p != aNode);

Node *newNode = new Node(x);

newNode->next = p;

prev->next = newNode;

}

}

0Vinay said on March 18, 2012

I have a question with regard…

say you have list as 3->*2->1 where the aNode points to 2 i.e its starts from 2 …now if you try to insert 4 in the list

then for the first time it goes inside the do while loop

prev is pointing to 2 and

P is pointing to 1

then the case 2 i.e

((prev->data > p->data) && (x data || x > prev->data))

[(2>1) && [(41)]]

is true and it breaks out of do while loop and

inserts 4 between 2 and 1.which is wrong

0Vinay said on March 18, 2012

sorry i wrote it wrong

[(2>1) && [(42)]]…which is true

0a said on April 15, 2012

IMO, a circular linked list data structure would have a head and rear pointer.

Various strategies are available for CRUD operations when this is data structure assumption.

Also another strategy could be using a header node containing a sentinel value and CRUD operations happen on the basis of this head node.

That way, we deal with circular linked list, pretty much like we would deal with a linear linked list.

0shantanu said on June 9, 2012

the following code shd work :

void insert(Node start, int val)

{

Node tmp = new Node(val);

//if list is empty

if(start == null) { tmp.next = tmp; return; }

//initialize current and greatest pointers

Node current = start;

Node greatest = start;

while(current.next != start)

{

//case 1: node lies between 2 values already present in the list

if(val > current.data && val greatest.data) greatest = current;

}

//now, value is either greater than all values in the list, or smaller than all values. //in any case, value should be inserted after the greatest node

tmp.next = greatest.next;

greatest.next = tmp;

}

0shantanu said on June 9, 2012

made a mistake in the while loop. shd be written as below

while(current.next != start)

{

//case 1: node lies between 2 values already present in the list

if(val > current.data && val greatest.data)

greatest = current;

}

0shantanu said on June 9, 2012

sorry for spamming, but I am not able to post the correct code here. Please follow the link for the correct implementation : http://phreakhoughts.blogspot.com/2012/06/problem-insert-given-value-into-sorted.html

0shantanu said on June 9, 2012

does not let me write the correct code !!!!

0shantanu said on June 9, 2012

while(current.next != start)

{

//case 1: node lies between 2 values already present in the list

if(val > current.data && val current.data)

{

greatest = current;

}

}

0phoenixwsl said on September 12, 2012

it seems u didn’t update your head node if x is the smallest value

0Song Qiang said on December 14, 2012

With all three cases

0Coder said on August 20, 2013

when there is only one node in the cyclic list, program will stop at the following line:

if (x data && x >= prev->data) break; // For case 1)

p->data is not valid because p is null pointer

0Zane said on October 3, 2013

I don’t understand why would someone use this data structure, you are going through the trouble of sorting the list, yet the way you access it gives away all the performance benefits. If it were a doubly linked list, i could see easy access to the smaller values from the node->prev and larger values from node->next.

0sachin said on November 23, 2013

Hi all, thanks a lot for great explanations. I have one request can someone write code in java?

0Shoumo said on January 10, 2014

Just use this method to add a new node and it will always enter it in a sorted way

0Rami said on January 27, 2014

void insert(Node * aNode, int x)

{

// handle NULL list case

if( aNode == NULL )

{

aNode = new Node(x);

aNode->next = aNode;

return;

}

while(

( aNode->next->v >= aNode->v && x >= aNode->next->v ) ||

( aNode->next->v v && x >= aNode->next->v ) )

{

aNode = aNode->next;

}

Node n = new Node(x)

n->next = aNode->nex;

aNode->next = n;

}

0sachin said on March 23, 2014

@Shoumo : it seems that your code is only for you have given head node. I’m i correct ? What if other node is given as input?

0Dipesh Gupta said on March 2, 2014

Hi admin,

I am doubtful about one case though. With your given linked list, lets say the value to be inserted is 0.

Although it may be inserted before 1 (or after 6) with the given code, but should not the headPointer (aNode) be now pointing to 0.

Because the list is sorted, it makes sense to start with the smallest element.

0hakki said on March 23, 2014

Actually your solution is unnecessarily complicated. Please see the following strightforward code. It handles all the cases mentioned.

+1hakki said on March 23, 2014

Sorry, ignore the previous post. There is a copy/paste mistake. See the following code.

0hakki said on March 23, 2014

there is a problem with code tag. It crops some parts while posting. I am sending without code tags this time. I hope it shows the code correctly.

public static Node insert(Node node, int x)

{

if(node == null)//empty list

{

Node newNode = new Node(x);

newNode.next = newNode;

return newNode;

}

Node start = node;

while(node.next != start)

{

if(node.val = x)

{

Node newNode = new Node(x);

newNode.next = node.next;

node.next = newNode;

return node;

}

else

{

node = node.next;

}

}

//if list has one value, min, max

Node newNode = new Node(x);

newNode.next = start;

node.next = newNode;

return node;

}

0ahmad omar said on July 14, 2014

what if insert for node in circular linked list as this ( void insert (const Type& newItem)) please help

0Lei Huang said on April 5, 2014

good

0roberti said on April 11, 2014

+1badcoder said on May 4, 2014

Can any one please check my code and let me know if I have done any mistake.

public ListNode insertIntoSortedCircularList(ListNode head, int val){

ListNode temp = new ListNode(val);

if(head == null){

head = temp;

head.setNext(head);

}else if (head.getData()>val){

temp.setNext(head.getNext());

head.setNext(temp);

temp.setData(head.getData());

head.setData(val);

}else{

ListNode current = head;

ListNode prev = null;

while(current.getNext() != head && current.getData()<val){

prev = current;

current = current.getNext();

}

if(current.getNext() == head && current.getData()<val){

temp.setNext(head);

current.setNext(temp);

}else{

temp.setNext(current);

prev.setNext(temp);

}

`}`

return head;

}

0badcoder said on May 4, 2014

Can any one please check my code and let me know if I have done any mistake?

0ptyyyyyy said on May 15, 2014

what if you want to insert 5 into a list starting from node 3->7->6->5->4?

it will fall into case 1 and return 3->5->7->6->5, which is not correct.

Am I missing something?

0A2Z Health Massage School said on August 14, 2014

Thanks for finally talking about >Insert into a Cyclic Sorted List | LeetCode <Liked it!

0http://guild.tk/Leave_a_reply_2153536 said on September 1, 2014

Do you mind if I quote a couple of your articles as long as I provide credit and sources back to your blog?

My website is in the exact same niche as yours and

my users would really benefit from a lot of the information you present here.

Please let me know if this okay with you.

Thanks a lot!

0