LinkedList插入问题

Question

我试图在链接列表中为位置0(即链接列表的开始)和其他位置(如在任何两个节点之间和在链接列表的末尾)编码插入。代码如下所示。但它似乎没有像预期的那样起作用。请告诉我哪里做错了。

#include <iostream>
using namespace std;
struct Node
{
int data;
Node *next;
};
void displayLL(Node *p)
{
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
}
Node *createLL(int A[], int n, Node *ll)
{
Node *tmp, *last;
ll = new Node;
ll->data = A[0];
ll->next = NULL;
last = ll;
for (int i = 1; i < n; i++)
{
tmp = new Node;
tmp->data = A[i];
tmp->next = NULL;
last->next = tmp;
last = tmp;
}
return ll;
}
int countNodesLL(Node *p)
{
int count = 0;
while (p != NULL)
{
count++;
p = p->next;
}
return count;
}
void InsertNodeLL(Node *p, int index, int value)
{
Node *tmp;
if (index < 0 || index > countNodesLL(p))
{
return;
}
tmp = new Node;
tmp->data = value;
// This should insert in the beginning of the Linked List - but it is not working.
if (index == 0)
{
tmp->next = p; // pointing next of tmp to p node
p = tmp;       // making tmp as the HEAD of linkedList
}
// This inserts after 1st node, in between two nodes and at the end of the LL
else
{
for (int i = 0; i < index - 1; i++)
{
p = p->next;
}
tmp->next = p->next;
p->next = tmp;
}
}
int main(int argc, char const *argv[])
{
Node *linkedList = NULL;
int A[] = {1, 2, 3, 4, 5, 6, 7, 8};
linkedList = createLL(A, 8, linkedList);
displayLL(linkedList);
cout << endl;
InsertNodeLL(linkedList, 0, 15);
displayLL(linkedList);
cout << endl;
InsertNodeLL(linkedList, 4, 10);
displayLL(linkedList);
return 0;
}

我得到下面的输出:

1 2 3 4 5 6 7 8 
1 2 3 4 5 6 7 8 
1 2 3 4 10 5 6 7 8 

预期输出:

1 2 3 4 5 6 7 8 
15 1 2 3 4 5 6 7 8 
15 1 2 3 4 10 5 6 7 8 

请告诉我代码有什么问题。

Answer 1

你犯了两个错误，首先你没有返回一个值回到链表，因为你通过值的指针，第二在你的插入函数，你也不返回一个值，以及你正在修改头变量，所以你失去了以前的值。而且你要在第5个位置插入，而不是第4个位置。当你在函数内部进行更改时，你只使用局部变量，所以在堆栈帧弹出后，链表不会更新。你可以使用一个全局变量来代替，但是如果你是按值传递的，如果你想改变main中的列表，你必须返回给调用者。这是我重新实现你的代码:'

#include <iostream>
using namespace std;
struct Node
{
int data;
Node* next;
};
void displayLL(Node* p)
{
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
}
Node* createLL(int A[], int n, Node* ll)
{
Node* tmp, * last;
ll = new Node;
ll->data = A[0];
ll->next = NULL;
last = ll;
for (int i = 1; i < n; i++)
{
tmp = new Node;
tmp->data = A[i];
tmp->next = NULL;
last->next = tmp;
last = tmp;
}
return ll;
}
int countNodesLL(Node* p)
{
int count = 0;
while (p != NULL)
{
count++;
p = p->next;
}
return count;
}
Node* InsertNodeLL(Node* p, int index, int value)
{
Node* tmp;
Node* tmp2;
if (index < 0 || index > countNodesLL(p))
{
return 0;
}
tmp = new Node;
tmp->data = value;
// This should insert in the beginning of the Linked List - but it is not working.
if (index == 0)
{
tmp->next = p; // pointing next of tmp to p node
p = tmp;
return p;       // making tmp as the HEAD of linkedList
}
// This inserts after 1st node, in between two nodes and at the end of the LL
else
{
tmp2 = p;
for (int i = 0; i < index - 1; i++)
{
tmp2 = tmp2->next;
}
tmp->next = tmp2->next;
tmp2->next = tmp;
return p;
}
}
int main(int argc, char const* argv[])
{
Node* linkedList = NULL;
int A[] = { 1, 2, 3, 4, 5, 6, 7, 8 };
linkedList = createLL(A, 8, linkedList);
displayLL(linkedList);
cout << endl;
linkedList = InsertNodeLL(linkedList, 0, 15);
displayLL(linkedList);
cout << endl;
linkedList = InsertNodeLL(linkedList, 5, 10);
displayLL(linkedList);
return 0;
}
`

Answer 2

#include <iostream>
using namespace std;
struct Node
{
int data;
struct Node *next;
} *first = NULL;
void create(int A[], int n)
{
int i;
struct Node *t, *last;
first = new Node;
first->data = A[0];
first->next = NULL;
last = first;
for (i = 1; i < n; i++)
{
t = new Node;
t->data = A[i];
t->next = NULL;
last->next = t;
last = t;
}
}
void Display(struct Node *p)
{
while (p != NULL)
{
cout << p->data << " ";
p = p->next;
}
}
int count(Node *p)
{
int count = 0;
while (p != NULL)
{
count++;
p = p->next;
}
return count;
}
void Insert(struct Node *p, int index, int x)
{
struct Node *t;
int i;
if (index < 0 || index > count(p))
return;
t = new Node;
t->data = x;
// When a node needs to be inserted at the beginning
if (index == 0)
{
t->next = first;
first = t;
}
// When a node needs to be inserted in between two nodes or at the last
else
{
for (i = 0; i < index - 1; i++)
p = p->next;
t->next = p->next;
p->next = t;
}
}
int main()
{
int A[] = {10, 20, 30, 40, 50};
create(A, 5);
Insert(first, 0, 5);
Display(first);
cout << endl;
Insert(first, 2, 15);
Display(first);
cout << endl;
return 0;
}

这个也可以!!