# Sorted Insert for Sorted Circular Linked List

This story was originally published here.

Trying to find the solution to this challenge may result in some of your guess running off to infinity and beyond. A close look at the edge cases and preparing some nested conditionals should give us the solution we are after.

#### Ground work

I’ll go on and start us off by saying that we have a list, sorted in ascending order, and the tail points back to the head of the list. The nodes are a basic struct with a data and next attribute. This completes our circularly linked list. Now how about inserting a new element into the list.

def insert(value)

#magic happens here…

end

Let’s say that we will traverse the list and use a pointer to the next node as a helper to remap the links when we do the insertion.

def insert(value)

current_node = @head_node

next_node = current_node.next

# iteration through loop here

end

Now we can traverse the list and keep track of where our new node will be pointing and where our current node doesn’t get left by the wayside.

#### Traverse until we find our insertion point

We will traverse the linked list until our next node has a value greater than the value we are trying to insert. This tells us where our new node will point too.

def insert(value)

current_node = @head

next_node = current_node.next

while value > next_node.data

current_node = next_node

next_node = current_node.next

end

new_node = Node.new(value, next_node)

current_node.next = new_node

end

After we break the loop we will create the new node and have it point to the next node. The current node will point to our new node. All is great right…?

Well no, if we are trying to enter a value that is greater than any value within the linked list we will fall right into a continuous loop.

#### Stomp out the edge case

To take care of this we can add a conditional to our loop that will break it when the next node has a value smaller than the current node. This implies that we have returned back to the beginning of the list. Let’s see what our final solution will look like.

def insert(value)

current_node = @head

next_node = current_node.next

while value > next_node.data

current_node = next_node

next_node = current_node.next

breakif next_node.data < current_node.data

end

new_node = Node.new(value, next_node)

current_node.next = new_node

end

The source code can be found here on my github.