Insert given node into the correct sorted position in the given sorted linked list

Given a list that is sorted in increasing order, and a single node, insert the node into the correct sorted position in the given list. The function should take an existing node, and just rearranges pointers to insert it into the list.

 

For example,

  sortedinsert

 


 

There are many possible solutions to this problem. The basic strategy is to iterate down the list looking for the place to insert the new node. That could be the end of the list, or a point just before a node which is larger than the new node. The three solutions presented handle the “head end” case in different ways…

 
C++ implementation –
 

Download   Run Code

Output:

1 -> 2 -> 4 -> 5 -> 6 -> 8 -> 9 -> null

 


 

Using Dummy Node

Another strategy is to use a temporary dummy node to take care of the first node case. The dummy node nothing but temporarily the first node in the list.

 
C++ implementation –
 

Download   Run Code

Output:

1 -> 2 -> 4 -> 5 -> 6 -> 8 -> 9 -> null

 


 

Using Local references

 
C++ implementation –
 

Download   Run Code

Output:

1 -> 2 -> 4 -> 5 -> 6 -> 8 -> 9 -> null

 
Source:
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂