使用C#-RemoveLast方法实现单链表

Question

我已经用C#实现了单链表。任何人都可以查看下面的代码并指出我的错误所在吗？

public int RemoveLast()
{
    if (Head != null)
    {
         var curNode = Head;

         while (curNode.Next != null)
         {
              curNode = curNode.Next;
         }

         var lastNodeValue = curNode.Value;

         curNode = null;
         Size--;
         return lastNodeValue;
     }

     return -1;
}

此函数不删除最后一个节点。我不知道出了什么问题。当while循环结束时，curNode中的node引用的next为null。这意味着这是最后一个节点。最后，我将此节点设置为null。但当我使用显示功能时。它还显示最后一个节点。这不是删除最后一个节点。

这里是我的显示功能：

    public string Display()
    {
        if (Head == null)
        {
            return string.Empty;
        }

        var curNode = Head;
        var builder = new StringBuilder();

        while (curNode.Next != null)
        {
            builder.Append($"{curNode.Value} ");
            curNode = curNode.Next;
        }

        builder.Append($"{curNode.Value} ");

        return builder.ToString();
    }

Answer 1

您需要创建curNode。上一个节点上的下一个值为null。'curNode'是一个局部变量，将其设置为null除了可能延长其GC寿命外，没有任何作用。

public int RemoveLast()
{
    if (Head != null)
    {
         var curNode = Head;
         var previousNode = null;

         while (curNode.Next != null)
         {
              previousNode = curNode;
              curNode = curNode.Next;
         }

         var lastNodeValue = curNode.Value;

         if (previousNode == null)
             Head = null;
         else
             previousNode.Next = null;
         Size--;
         return lastNodeValue;
     }

     return -1;
}

Answer 2

[x] -> [x] -> [x] -> null
               ^
               curNode (becomes null)
           ^
           this reference still exists

执行curNode=null操作时，不会更改列表中的任何引用curNode变量仅更改，它在操作前指向最后一个元素，之后变为null。

请尝试始终在最后一个节点之前保留对该节点的引用：

public int RemoveLast()
{
    if (Head != null)
    {
        var curNode = Head;
        // Corner case when there is only one node in the list
        if (Head.Next == null)
        {
            Head = null;
            Size--;
            return curNode.value;
        }

        var beforeLastNode = curNode;
        curNode = curNode.Next;
        while (curNode.Next != null)
        {
            beforeLastNode = curNode;
            curNode = curNode.Next;
        }

        var lastNodeValue = curNode.Value;

        beforeLastNode.Next = null;
        Size--;
        return lastNodeValue;
    }

    return -1;
}

Answer 3

您需要转到最后一个节点，将其Next更改为null：

public int RemoveLast()
{
    if (Head != null)
    {
        var curNode = Head;

        while (curNode.Next?.Next != null)
        {
            curNode = curNode.Next;
        }

        var lastNodeValue = curNode.Next?.Value ?? -1;
        curNode.Next = null;
        Size--;
        return lastNodeValue;
    }

    return -1;
}

请注意，如果您还希望Head设置为null（如果它是唯一的节点），那么您可以这样做：

public int RemoveLast()
{
    if (Head != null)
    {
        var curNode = Head;

        while (curNode.Next?.Next != null)
        {
            curNode = curNode.Next;
        }

        int lastNodeValue;

        if (Head.Next == null)
        {
            lastNodeValue = Head.Value;
            Head = null;
        }
        else
        {
            lastNodeValue = curNode.Next?.Value ?? -1;
        }
        curNode.Next = null;
        Size--;
        return lastNodeValue;
    }

    return -1;
}

不过，我不得不说，这个Head属性看起来有点可疑——它可能应该属于不同的类。