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:

  1. prev→val ≤ x ≤ current→val:
  2. Insert between prev and current.
  3. 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.
  4. 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.

VN:F [1.9.22_1171]
Rating: 4.6/5 (50 votes cast)
Insert into a Cyclic Sorted List, 4.6 out of 5 based on 50 ratings

69 responses to Insert into a Cyclic Sorted List

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

    VA:F [1.9.22_1171]
    +1
    • The problem is you don’t know it has all duplicates until you traverse back to the starting point.

      VN:F [1.9.22_1171]
      +1
      • 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?

        VA:F [1.9.22_1171]
        0
      • read it again and figured out your logic

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

        VA:F [1.9.22_1171]
        0
        • 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.

          VN:F [1.9.22_1171]
          0
  2. 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.

    VA:F [1.9.22_1171]
    0
    • 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.

      VN:F [1.9.22_1171]
      +1
      • 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.

        VA:F [1.9.22_1171]
        +1
        • There’s a typo in the above comment, it’s in the 2nd case

          VA:F [1.9.22_1171]
          0
        • 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.

          VA:F [1.9.22_1171]
          0
  3. I don’t think we should make the assumption that the list is ASC sorted.

    VA:F [1.9.22_1171]
    0
    • You can first find whether list is sorted in ASC or DESC order and then check conditions accordingly.

      VA:F [1.9.22_1171]
      0
      • of course we can… my point is that we definitely need this

        VA:F [1.9.22_1171]
        0
        • 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).

          VA:F [1.9.22_1171]
          0
  4. 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.

    VA:F [1.9.22_1171]
    +1
    • Thanks for pointing out this mistake. Another reader has pointed out below, and I just noticed it. Sorry for not noticing your comment earlier.

      VN:F [1.9.22_1171]
      0
  5. “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.

    VA:F [1.9.22_1171]
    0
    • 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.

      VA:F [1.9.22_1171]
      0
  6. This question has taught me to check all the edge cases before we code !! Thanks

    VN:F [1.9.22_1171]
    0
  7. 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

    VA:F [1.9.22_1171]
    0
  8. sorry the line is
    if ((x data) && (p == aNode))
    {
    aNode = newNode;
    }

    VA:F [1.9.22_1171]
    0
  9. sorry again
    if ((p->data > x ) && (p == aNode))
    {
    aNode = newNode;
    }

    VA:F [1.9.22_1171]
    0
  10. 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 :)

    VN:F [1.9.22_1171]
    0
  11. 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;
    }

    }

    VA:F [1.9.22_1171]
    0
  12. 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 value 1.The code will insert a new node after the existing one breaking the sorted order.

    VA:F [1.9.22_1171]
    0
    • 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.

      VN:F [1.9.22_1171]
      0
      • 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?

        VA:F [1.9.22_1171]
        0
        • 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?

          VN:F [1.9.22_1171]
          0
  13. At this point you are incorrect. None of the 2 conditions are satisfied when we try to insert the value 1 in a list wich has only one node with value 2.
    Neither the first

    nor the second

    . So you go out of the while loop 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?

    VA:F [1.9.22_1171]
    0
    • 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.

      VN:F [1.9.22_1171]
      0
    • 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.)

      VA:F [1.9.22_1171]
      0
  14. 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 if is 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

    VA:F [1.9.22_1171]
    0
    • 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! :)

      VN:F [1.9.22_1171]
      0
    • 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!

      VN:F [1.9.22_1171]
      0
  15. 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 sorted cyclic 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 ?

    VA:F [1.9.22_1171]
    0
  16. @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 break out of the while loop 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

    VA:F [1.9.22_1171]
    0
  17. 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 …

    VN:F [1.9.22_1171]
    0
  18. 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;
    }
    }

    VN:F [1.9.22_1171]
    0
  19. 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

    VA:F [1.9.22_1171]
    0
  20. sorry i wrote it wrong
    [(2>1) && [(42)]]…which is true

    VA:F [1.9.22_1171]
    0
  21. a 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.

    VA:F [1.9.22_1171]
    0
  22. 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;

    }

    VA:F [1.9.22_1171]
    0
  23. does not let me write the correct code !!!!

    VA:F [1.9.22_1171]
    0
  24. 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;
    }

    }

    VA:F [1.9.22_1171]
    0
  25. it seems u didn’t update your head node if x is the smallest value

    VA:F [1.9.22_1171]
    0
  26. With all three cases

    VN:F [1.9.22_1171]
    0
  27. 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

    VN:F [1.9.22_1171]
    0
  28. 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.

    VN:F [1.9.22_1171]
    0
  29. Hi all, thanks a lot for great explanations. I have one request can someone write code in java?

    VN:F [1.9.22_1171]
    0
  30. Just use this method to add a new node and it will always enter it in a sorted way

    VA:F [1.9.22_1171]
    0
    • 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;
      }

      VA:F [1.9.22_1171]
      0
    • @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?

      VA:F [1.9.22_1171]
      0
  31. 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.

    VA:F [1.9.22_1171]
    0
  32. Actually your solution is unnecessarily complicated. Please see the following strightforward code. It handles all the cases mentioned.

    VA:F [1.9.22_1171]
    +1
    • Sorry, ignore the previous post. There is a copy/paste mistake. See the following code.

      VA:F [1.9.22_1171]
      0
    • 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;

      }

      VA:F [1.9.22_1171]
      0
    • what if insert for node in circular linked list as this ( void insert (const Type& newItem)) please help

      VA:F [1.9.22_1171]
      0
  33. good

    VN:F [1.9.22_1171]
    0
  34. VN:F [1.9.22_1171]
    +1
  35. 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;
    }

    VN:F [1.9.22_1171]
    0
  36. Can any one please check my code and let me know if I have done any mistake?

    VN:F [1.9.22_1171]
    0
  37. 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?

    VN:F [1.9.22_1171]
    0
  38. Thanks for finally talking about >Insert into a Cyclic Sorted List | LeetCode <Liked it!

    VA:F [1.9.22_1171]
    0
  39. VN:F [1.9.22_1171]
    0
  40. // CircularLinkedList.cpp : Defines the entry point for the console application.
    //

    #include “stdafx.h”
    #define N 5
    //#define N 4
    //#define N 3
    //#define N 2
    //#define N 1

    typedef struct node_tag
    {
    int data;
    node_tag* link;
    }node;

    void printCircularLinkedList(node* tail)
    {
    if (tail == NULL)
    {
    printf(“\nLinked List is empty”);
    return;
    }

    node *cur;
    cur = tail;

    do
    {
    cur = cur->link;
    printf(“%d\n”, cur->data);
    } while (cur != tail);
    }

    node* addNode(node *tail, int x)
    {
    node *p = new node;
    p->data = x;
    if (tail == NULL)
    p->link = p;
    else
    {
    p->link = tail->link;
    tail->link = p;
    }
    tail = p;
    printf(“\n Added node with data %d\n”, x);
    return tail;
    }

    node* createCircularLinkedList(node* tail)
    {
    int i, x;
    printf(“Enter elements\n”);
    for (i = 0; i data = x;

    if (tail == NULL)
    {
    p->link = p;
    tail = p;
    return tail;
    }

    if (tail->link == tail)
    {
    tail->link = p;
    p->link = tail;
    return tail;
    }

    prev = tail;
    cur = tail->link;
    if (x data)
    {
    while (x data)
    {
    prev = cur;
    cur = cur->link;
    if (prev->data > cur->data)
    break;
    }
    if (x > cur->data)
    {
    while (x > cur->data)
    {
    prev = cur;
    cur = cur->link;
    }
    }
    }
    else
    {
    while (x > cur->data)
    {
    prev = cur;
    cur = cur->link;
    if (prev->data > cur->data)
    break;
    }
    }
    p->link = cur;
    prev->link = p;
    return tail;
    }

    int _tmain(int argc, _TCHAR* argv[])
    {
    node *tail;
    tail = NULL;
    int option, x;
    tail = createCircularLinkedList(tail);

    //printCircularLinkedList(tail);

    do
    {
    printf(“\nEnter option:\n 1. Print \n 4. Insert \n 9. Exit \n”);
    scanf_s(“%d”, &option);

    switch (option)
    {
    case 1:
    printCircularLinkedList(tail);
    break;
    case 4:
    printf(“\nEnter element to be Inserted in a sorted Circular linked List:\n”);
    scanf_s(“%d”, &x);
    tail = insertNodeCircularLinkedList(tail, x);
    printf(“\nLinked list after Insertion operation:\n”);
    printCircularLinkedList(tail);
    break;
    case 9:
    return 0;
    default:
    printf(“\nEnter a vaid option\n”);
    }
    }
    while (true);
    return 0;
    }

    VA:F [1.9.22_1171]
    0
  41. Hello! Your article rocks at the same time as getting a legitimate wonderful realize!??

    VA:F [1.9.22_1171]
    0
  42. Si estáis buscando el índice de Bricodepot aqui os dejo unos enlaces
    para que los comprobeis, espero que os sean de asistencia

    VA:F [1.9.22_1171]
    0

Leave a reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.