时间戳

首页 > 解决方案 > 此函数是否将新节点添加到链表的末尾？

c++ - 此函数是否将新节点添加到链表的末尾？

问题描述

我想知道，这是否会在列表末尾插入一个节点？假设我有一个 1->2->3->8->NULL 的链表，我想插入一个数据为 9 的新节点。它将递归遍历到 NULL。当 head 指向 NULL 时，head = nextNode 不起作用。还是 head 仍然指向 8 的节点？谢谢你。

我只想知道这可以在列表末尾插入一个节点吗？我不这么认为。

void insert(Node *&head, int data) {
    if (head == NULL || data <head ->data) {
        Node *nextNode = new Node;
        nextNode->data = data;
        nextNode->next = head;
        head= nextNode;
    } else {
        insert(head->next, data);
    }
}

标签： c++sortingrecursioninsertsingly-linked-list

解决方案

这个条件

if ( head == NULL || data < head->data )

对于包含节点序列的列表中的每个节点，is 不计算为 true，例如

1->2->3->8->NULL

因为 data 的值9不小于现有节点的任何 data 值。

因此，函数将被递归调用，直到下一个节点等于 NULL（即当函数将参考最后一个节点的数据成员 next 等于 nullptr 时被调用）。结果，新节点被附加到列表的尾部。也就是说，列表中最后一个值为 NULL 的指针将被替换为新节点。因此节点按升序插入到列表中。

这是一个演示程序。

#include <iostream>

struct Node
{
    int data;
    Node *next;
};

void insert( Node * &head, int data ) 
{
    if ( head == nullptr || data < head ->data ) 
    {
        head = new Node { data, head };
    } 
    else 
    {
        insert( head->next, data );
    }
}

std::ostream & output( const Node *head, std::ostream &os = std::cout )
{
    for ( ; head != nullptr; head = head->next)
    {
        os << head->data << " -> ";
    }

    return os << "null";
}

int main() 
{
    Node *head = nullptr;

    for ( int data : { 3, 8, 1, 2, 9 } )
    {
        insert( head, data );
        output( head ) << '\n';
    }

    return 0;
}

它的输出是

3 -> null
3 -> 8 -> null
1 -> 3 -> 8 -> null
1 -> 2 -> 3 -> 8 -> null
1 -> 2 -> 3 -> 8 -> 9 -> null

为了清楚起见，考虑一个包含两个节点的列表，其中包含数据1和3.

head  |node A with value 1|next B|  |node B with value 3| next nullptr|
 |______________|              |______________|

并且您正在尝试插入一个具有 value 的节点2。

该函数被调用

insert( head, 2 );

head->data 等于 1 不大于 2。所以函数调用如下

insert( ( node A )->next, 2 );

( node A )->next->data 等于 3 大于 2。

因此，您必须将 ( node A )->next 替换为值 2 的新创建节点的地址。

head  |node A with value 1|next C|  |node B with value 3| next nullptr|
 |______________|              |              |
                               |              |
          |node C with value 2 | the value of next B of node A|

推荐阅读