如何将元素添加到链表的末尾？

Question

如何将元素添加到链表的末尾？

3

我尝试搜索答案，但似乎找不到与我的问题相匹配的内容。我正在为学校做一个模板链接列表，但是遇到了很多错误。目前我只需要帮助解决其中一个问题。我应该将一个元素附加到一个链接列表的末尾，但是我们得到以下错误：

append(ListNode)

起初，我想：“好的，创建一个新节点，在末尾插入……”但是我重新阅读了一遍，发现我还需要创建另一个函数来将两个链表连接在一起。因此，我认为我必须在已经存在的元素后面追加链接列表。这样，当我进行拼接时，我可以使用我的追加函数将它们附加在一起。至少……这只是我的想法。

所以，起初，我做了：

template<typename NODETYPE> 
bool List<NODETYPE>::append(NODETYPE &value)
{
    ListNode<NODETYPE> *newPtr = getNewNode(value); //creates new node

    if(isEmpty()) //checks if list is empty
    {
        firstPtr = lastPtr = newPtr;
        return true;
    }
    else //inserts new node at end of list
    {
        ListNode<NODETYPE> *tempPtr = lastPtr;

        tempPtr->nextPtr=newPtr;
        lastPtr = newPtr;
        return true;
    }
}

但是由于这仅附加一个新节点，我不能使用它。有没有一种方法可以附加已经制作的节点？例如：将另一个链接列表附加到前一个列表上？

我的concat（与我搜索的其他人不同）只使用一个链接列表。之前的链接列表对象调用函数，然后附加一个列表。

concat(&List)

我很困惑，希望能得到帮助，谢谢！

- Nelliel

3个回答

0

要将list2连接到list1这样的列表中，您需要将list2的头节点附加到list1的最后一个节点上，并更新lastPtr，类似于下面的示例代码：

//apart from checking for basic sanity like empty list and things 
// suppose argument passed is ListNode list2
        ListNode<NODETYPE> *tempPtr = lastPtr;

        tempPtr->nextPtr=list2;
        tempPtr = list2;
        while(tempPtr->next != NULL) {
              tempPtr = tempPtr->next;
        }
         lastPtr = tempPtr;

        return true;

- Rndm

这可能听起来有点傻，我已经想出你给我的那部分了，但还是谢谢你确认一下——但是我该如何为此设置原型？我以前从未引用过对象（链表中的链表），我已经试图解决这个问题好几天了。我放置了void List<NODETYPE>::concat(List)，但我知道那是错误的...有没有特殊的方法可以做到这一点？或者如何在代码中单独引用不同的列表？ - Nelliel

为了设置原型，应该像这样：bool List<NODETYPE>::concat(ListNode *list2) - 你只需传递指向链表头的指针。 - Rndm

谢谢:D 嗯，我怎么才能检查第二个列表是否为空？我知道我在问很多问题 --> 我有点沮丧，因为我不太清楚。 - Nelliel

1

你只需要在一个if语句中检查list2是否为NULL。 - Rndm

0

在编程中，就地连接列表的确切步骤取决于特定的实现细节。最简单的情况是单向链表，在这种情况下，只需将第二个头链接到旧尾部即可。如果您有一个尾指针，请记得更新它。对于双向链表，您还需要将第二个头链接回旧尾部。如果您使用了哨兵节点，请记得也要处理它。

编辑：请忽略此内容，我混淆了，以为您可能正在尝试使用标准列表。

在C++中，std::list是带有哨兵节点的双向链表，这使得连接变得非常复杂。此外，您不应该擅自更改内部结构。如果您想使用标准容器，则需要遵守其公共API，否则会发生糟糕的事情。幸运的是，我相信有一个库函数可以用于连接。

- Antimony

我不能使用双向链表或库中的任何其他东西，因为我认为我们还没有学到任何真正有助于解决这个问题的东西。一切都是从头开始。但是，主函数中的连接看起来像这样：Li.concat(Li2);Li2也是一个对象。Li和Li2都是int类型。但是追加操作让我感到困惑。我会得到这样的结果： Li2.append(5);我看着这个，仍然认为我必须创建一个新节点并将其附加到末尾。我想我已经用其他函数超负荷了...现在我对所有事情都感到困惑。 - Nelliel

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Aamir · Accepted Answer

首先，您需要更改append方法的签名，以便传递一个ListNode*，并且无论它是单个节点还是整个链表，都将其附加。之后，您的代码应该如下所示：

template<typename NODETYPE> 
bool List<NODETYPE>::append(ListNode<NODETYPE>* newPtr)
{
    //ListNode<NODETYPE> *newPtr = getNewNode(value); //creates new node

    if(isEmpty()) //checks if list is empty
    {
        firstPtr = lastPtr = newPtr;
        return true;
    }
    else //inserts new node at end of list
    {
        ListNode<NODETYPE> *tempPtr = lastPtr;

        tempPtr->nextPtr=newPtr;
        lastPtr = newPtr;
        while(lastPtr->nextPtr != NULL)
            lastPtr = lastPtr->nextPtr;
        return true;
    }
}

我还没有编译它，所以可能会有一些错误，但你可以理解我的意思。