c++ - 单向链表添加节点(支持前端、尾部、中间添加)

Question

我正在尝试编写一个“添加”函数，该函数接受节点中保存的值(表示为“n”)，以及节点要添加到链表中的位置(表示为“pos”)。

我看到代码中有 3 个单独的添加函数 - addAtBeginning、addAtMiddle、addAtEnd，但我想要一个添加函数来完成所有这些。

我已经为 add(int n, int pos) 编写了代码，但它没有给我预期的输出。

例如，在我的 main 中，我有:

LinkedList num;
num.add(5,1);


num.add(6,2);

num.add(7,2);
num.printList();

我期待输出:5 7 6，(因为 7 将移到第二个位置，然后 6 将移到第三个位置)，除了我得到的输出:5 6 7，其中 7被添加到第 3 个位置。

此外，我已经编写了我的 Node 类和 LinkedList 类。我一直在以较小的增量测试我在这些类中的功能，除了我的添加功能外，其他一切似乎都很好。

Node * newNode = new Node();

newNode->setValue(n); //Node gets value n

int i=1; //ie. first position is 1, not 0

Node * current = head;

if (current == nullptr) //ie. then new node IS the head
{
    head = newNode;
    head->next=nullptr;
    return;
}

if (current->next==nullptr) //adding to end of list
{

    current->next = newNode;
    newNode->next = nullptr;

}
else //if inserting Node at middle, (neither at beginning or end)
{


    while ( i<pos && current->next != nullptr) //traverse thru list
    {
        current=current->next;
        i = i+1;
    }

    Node * oldNext = current->next; 

    current -> next = newNode;

    newNode -> next = oldNext;



}

我编译的时候没有报错。

Answer 1

您的 while 条件有一个小问题，描述如下:

i=1;
while ( i<pos && current->next != nullptr) //traverse thru list
{
    current=current->next;
    i = i+1;
}

现在想想这个场景，我想在 6 的位置插入节点，也就是位置 2。

根据你的代码，我的 pos 应该是 2 对吗？根据您的代码，这是出现问题的地方:

while(i

接下来会发生什么

• 当i =1时，i
• 现在i变成了2，因为i=i+1;
• 现在 i 不小于 pos，所以它跳出循环，记住你的当前节点指向头的下一个节点。

Node * oldNext = current->next;

current -> next = newNode;

newNode -> next = oldNext;

这里发生的是你的旧 next 指向第 3 个节点，因为当前节点是第 2 个节点。

您需要通过更改循环条件来修复它，以便循环停止在需要更改的前一个节点的 i< pos-1 处。