Inserting into sorted linked list?

Question

I'm very new to coding and I couldn't understand the error in my code, I'd be very grateful for any help.

So the code works fine except for the last element because the element after that is null and I couldn't handle it (I'm very new).

The problem is with the last part.

public static void InsertingIntoSortedLinkedList(int value, int key)
            {
                Node m = new Node();
                m.value=value;
                m.key=key;
                if (root==null)
                {
                    m.Next = null;
                    root = m;
                }
                else
                {
                    if (key<root.key)
                    {
                        m.Next = root;
                        root = m;
                    }
                    else
                    {
                        Node temp1 = root;
                        Node temp2 = null;
                        while ((temp1!=null)&&(temp1.key<key))
                        {
                            temp2 = temp1;
                            temp1 = temp1.Next;
                        }
                        if (temp1==null)
                        {
                            m.Next = null;
                            temp2.Next=m;
                        }
                        else
                        {
                            m.Next = temp1;
                            if (temp2!=null)//I either put this here and the last element is lost or I got a NullReferenceException. What should I change?
                            {
                                temp2.Next = m;

                            }
                        }
                    }
                }


}

Thank you for your help.

Answer 1

One situation where you may find a problem is when you insert a value equal to the root value - those values will be skipped because you are trying to insert BEFORE the matching item and not updating the root reference.

The solution is to either insert after the matching value - this can be done by changing the line

while ((temp1!=null)&&(temp1.key<key))

to

while ((temp1 != null) && (temp1.key <= key))

OR by inserting at the root element by changing the line

if (key<root.key)

to

if (key <= root.key)

OR by updating the root value when inserting before

if (temp2!=null)
{
  temp2.Next = m;
}
else
  root = m;

Any one of the changes should fix the problem