在单个链表中的任何索引处插入新节点

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

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

这是函数，注意只有双指针，索引和数据参数。

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

这是调用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 ] 

我知道如何在头部添加新节点，但不知道如何添加新节点。 我的想法是

 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; } 

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

Answer 1

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

其他3例是

• 插入列表的开头
• 插入列表中间
• 插入列表末尾。

保持计数并循环遍历列表中的所有元素。 此计数将帮助您跟踪索引。

到达节点后，必须插入新节点

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

完整的源代码在这里

Answer 2

当index == 0时你必须处理一个特殊情况，headRef将需要更新。 或者索引是否大于列表中的元素数。 插入将失败。 否则，请查看下面的示例代码。

 int insertN(struct node** headRef, int index, int data) { /* invalid headRef */ if (!headRef) { return 0; } /* insert node at index */ int i; struct node* new = (struct node *)malloc(sizeof(*node)); struct node *scan = *headRef; new->data = data; new->next = 0; /* new head of list */ if (scan == NULL && index == 0) { /* new head node */ new->next = *headRef; *headRef = new; return 0; } /* while not at end of list and not at index */ for (i = 0; scan != NULL && i <= index; i++) { if (i == index) { /* move what was here to next node and put in new node */ new->next = scan->next; scan->next = new; } else { /* advance to next entry in list */ scan = scan->next; } } /* scan == NULL indicates reached end of list before index */ return (scan != NULL); }