Как настроить указатели головы, хвоста при создании LinkedList - PullRequest
Новая
       64

Как настроить указатели головы, хвоста при создании LinkedList

0 голосов
/ 09 октября 2018

Я делаю простую реализацию LinkedList.Мое испытание: 

#include<bits/stdc++.h>

using namespace std;

class ListNode
{
public:
    ListNode* next;
    int val;
    ListNode(int x) : val(x), next(NULL) {}
};

int main()
{
    ListNode* head = NULL;
    ListNode* tail;
    int data;
    cout<<"Enter data. Enter -1 to terminate insertion"<<endl;
    while(1)
    {
        cin>>data;
        if(data != -1)
        {
            if(head == NULL)
            {
                head = new ListNode(data); // Returns the address of a new ListNode and stores it in head
                tail = head->next; // tail now points to head's next
            }
            else
            {
                tail = new ListNode(data); // address of a new ListNode is in tail
                tail = tail->next; // Tail now points to the new ListNode's next
            }
        }
        else
            break;
    }
    tail = NULL; // Tail ends with a NULL
    while(head)
    {
        cout<<head->val<<" ";
        head = head->next;
    }
}

Когда я ввожу 1, 2, 3: я ожидаю, что Связанный список будет сформирован как 1->2->3->NULL.

Однако Связанный список всегда только первыйэлемент 1->NULL

Я запустился на отладчике и, действительно, head->next всегда NULL.Но я не понимаю почему.Я специально меняю голову рядом с новым ненулевым адресом ListNode, когда я делаю tail = new ListNode(data), но, видимо, этого не происходит.Куда я иду не так?

Вот код: http://cpp.sh/6ardx

1 Ответ

0 голосов
/ 09 октября 2018

Проблема : tail всегда NULL.Как вы хотите установить соединение между tail и добавленным узлом в вашем списке, когда tail имеет значение NULL?

Когда список пуст и вы создаете первый узел, после вставки первого узла head и tail должны указывать на один и тот же узел.Измените 

        if(head == NULL)
        {
            head = new ListNode(data); // Returns the address of a new ListNode and stores it in head
            tail = head->next; // tail now points to head's next
        }

на 

        if(head == NULL)
        {
            tail = head = new ListNode(data); // Returns the address of a new ListNode and stores it in head
        }

вторую проблему, когда вы добавляете в конец списка, вам нужно обновить tail->next, чтобы он указывал на вставленный узел, поэтому измените 

        tail = new ListNode(data); // address of a new ListNode is in tail
        tail = tail->next; // Tail now points to the new ListNode's next

до 

        tail->next  = new ListNode(data); // address of a new ListNode is in tail
        tail = tail->next; // Tail now points to the new ListNode's next
...