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

Download   Run Code

Output:

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

Java

Download   Run Code

Output:

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

 

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

Download   Run Code

Output:

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

Java

Download   Run Code

Output:

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

 

3. Using Local references

C

Download   Run Code

Output:

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

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
Notify of