链表插入问题

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

你犯了两个错误，首先你没有 return 一个值返回链表，因为你按值传递了指针，第二个在你的插入函数中你也没有 return一个值以及您正在修改 head 变量，因此您丢失了以前的值。您还想在第 5 个位置而不是第 4 个位置插入。当您在函数内部进行更改时，您仅使用局部变量，因此在弹出堆栈框架后，您的链表不会更新。您可以改用全局变量，但是如果您按值传递，如果您希望更改 main 中的列表，则必须 return 返回给调用者。这是我对您的代码的重新实现：`

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

这个也行！！

链表插入问题

LinkedList Insert Issue

c++

linked-list

structure