在单个链表中的任何索引处插入新节点 [英] insert new node at any index within a single linked list

问题描述

我将如何创建一个允许我在链表中​​的任何索引处插入新节点的函数?这是结构:

how would i go about creating a function that will allow me to insert a new node at any index within a linked list? here's the struct:

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

这是函数，注意只有一个双指针、索引和数据参数.

here's the function, note there's only a double pointer, index, and data parameter.

void insertN(struct node** headRef, int index, int data);

这是调用 insertN 后的结果:

and here's what the result should look like after calling insertN:

[ HEAD ] -> [ 0 ] -> [ 15 ] -> [ 10 ] -> [ 5 ] -> [ NULL ]
insertN( &head, 3, -44);
[ HEAD ] -> [ 0 ] -> [ 15 ] -> [ 10 ] -> [ -44 ] -> [ 5 ] -> [ NULL ]
insertN( &head, 4, -55);
[ HEAD ] -> [ 0 ] -> [ 15 ] -> [ 10 ] -> [ -44 ] -> [-55 ] -> [ 5 ] -> [ NULL ]
insertN( &head, 0, -66);
[ HEAD ] -> [ -66 ] -> [ 0 ] -> [ 15 ] -> [ 10 ] -> [ 5 ] -> [ NULL ]

我知道如何向头部添加一个新节点，但在任何时候都不知道.我的想法是

i know how to add a new node to the head, but not at any point. the way i was thinking was

void insertN(struct node** headRef, int index, int data) {
    struct node* new;
    int i;
    for (i = 0; i <= index; i++) {
        if (i == index) {
            /* move what was here to next node and put in new node */
        }
    }

    return;
}

我只是不确定如何去做这一切，因为如果节点中有东西，我也必须移动所有后续节点.

i just am unsure how to go about doing all this, because if something was in the node, i have to move all subsequent nodes as well.

推荐答案

如下图所示，需要在两个节点之间插入节点.

As you can see in the image below, you need to insert the node between two nodes.

另外三个案例是

• 在列表开头插入
• 在列表中间插入
• 在列表末尾插入.

维护一个计数并遍历列表中的所有元素.这个数将帮助您跟踪索引.

Maintain a count and loop through all the elements in the list. This count will help you keep track of the index.

到达节点后，必须在其中插入新节点

Once you reach the node, where you have to insert the new node

• 创建新节点
• 将上一个节点的下一个指针指向新节点.
• 将新节点的下一个指针指向当前节点.

完整源代码可用这里

这篇关于在单个链表中的任何索引处插入新节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！