使用 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 中节点的引用，其 next 为 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.Next 值为空。 '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

您需要转到 last-but-one 节点，并将其 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 属性看起来有点可疑 - 它可能应该属于另一个 class.

Answer 3

[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 4

好的各位，在你们的帮助下，我重写了这个方法，满足了所有的要求，如果链表只有一个节点，则设置为HeadNode null。所以我们开始吧：

    public int RemoveLast()
    {
        if (HeadNode != null)
        {
            var currNode = HeadNode;
            var prevNode = HeadNode;

            if (HeadNode.Next == null)
            {
                HeadNode = null;
                Size--;
                return currNode.Value;
            }

            while (currNode.Next != null)
            {
                prevNode = currNode;
                currNode = currNode.Next;
            }

            prevNode.Next = null;
            Size--;
            return currNode.Value;
        }

        return -1;
    }

感谢在此主题中做出贡献的所有人。快乐编码:)

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

Singly Linked List Implementation using C# - RemoveLast Method

c#

singly-linked-list