c# - 插入排序链表？

Question

我是编码的新手，我无法理解我的代码中的错误，如果有任何帮助，我将不胜感激。

所以除了最后一个元素之外，代码工作正常，因为最后一个元素为空，我无法处理它(我是新手)。

问题出在最后一部分。

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;

                            }
                        }
                    }
                }


}

感谢您的帮助。

Answer 1

您可能会发现问题的一种情况是当您插入一个等于根值的值时 - 这些值将被跳过，因为您试图在匹配项之前插入而不是更新根引用。

解决方案是在匹配值之后插入 - 这可以通过更改行来完成

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

到

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

或者通过改变行在根元素处插入

if (key<root.key)

到

if (key <= root.key)

或者通过在之前插入时更新根值

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

任何一项更改都应该可以解决问题