Ошибка при создании связанного списка из другого связанного списка?

Question

Я создаю связанный список из другого связанного списка. Но второй связанный список не формируется, и при запуске программы появляется сообщение об утечке памяти.

Вот фрагмент кода, который беспокоит -

Node *rearrangeLinkedList(Node *head){

    printLinkedList(head);

    int lengthoflist = 0;

    Node *temp = head;

    while (temp!=NULL)
    {
        lengthoflist++;
        temp=temp->next;
    }   

    Node *secondList = NULL;

    // just a variable node to store the head of second linked list-
    Node *headOfSecondList = secondList;

    int count=1;

    while (count<=lengthoflist/2)
    {
        Node *temproary = new Node();
        temproary->data=head->data;
        temproary->next=NULL;
        secondList=temproary;
        secondList=secondList->next;
        head=head->next;
        count++;
    }

    printLinkedList(headOfSecondList);

}

printLinkedList () прекрасно печатает выходящий список, но не второй связанный список.

Answer 1

Если я правильно понял, функция пытается построить новый список из первой половины узлов существующего списка.

Если это так, то нет необходимости вычислять количество узлов в исходном списке. , Это неэффективно.

Вы объявили функцию с типом возврата Node *.

Node *rearrangeLinkedList(Node *head );

, но функция ничего не возвращает.

Внутри функции переменная headOfSecondList устанавливается один раз на nullptr и никогда не изменяется.

Node *secondList = NULL;
Node *headOfSecondList = secondList;

В течение времени l oop новые узлы не объединяются в список. Всегда изменяется переменная secondList, а ее следующий элемент данных всегда устанавливается в NULL. Таким образом, возникают многочисленные утечки памяти.

while (count<=lengthoflist/2)
{
    Node *temproary = new Node();
    temproary->data=head->data;
    temproary->next=NULL;
    secondList=temproary;
    secondList=secondList->next;
    head=head->next;
    count++;
}

Функция может быть записана следующим образом.

Node * rearrangeLinkedList( Node *head )
{
    Node *new_head = nullptr;
    Node **tail = &new_head;

    Node *first = head, *current = head;

    while ( current != nullptr && ( current = current->next ) != nullptr )
    {
        current = current->next;

        *tail = new Node();
        ( *tail )->data = first->data;
        ( *tail )->next = nullptr;

        first = first->next;
        tail = &( *tail )->next;
    }

    return new_head;
}

Для демонстрации подхода без подсчета количества узлов в списке источников, которое как Я уже указывал, что здесь неэффективна демонстрационная программа с шаблоном класса List.

#include <iostream>

template <typename T>
class List
{
private:
    struct Node
    {
        T data;
        Node *next;
    } *head = nullptr;

public:
    List() = default;
    ~List()
    {
        while ( head )
        {
            Node *current = head;
            head = head->next;
            delete current;
        }
    }

    List( const List<T> & ) = delete;
    List<T> & operator =( const List<T> & ) = delete;

    void push_front( const T &data )
    {
        head = new Node { data, head };
    }

    List<T> & extract_half( List<T> &list ) const
    {
        Node **tail = &list.head;

        while ( *tail ) tail = &( *tail )->next;

        Node *first = this->head, *current = this->head;

        while ( current != nullptr && ( current = current->next ) != nullptr )
        {
            current = current->next;
            *tail = new Node { first->data, nullptr };
            first = first->next;
            tail = &( *tail )->next;
        }

        return list;
    }

    friend std::ostream & operator <<( std::ostream &os, const List &list )
    {
        for ( Node *current = list.head; current; current = current->next )
        {
            os << current->data << " -> ";
        }

        return os << "null";
    }
};

int main() 
{
    List<int> list1;

    const int N = 10;

    for ( int i = N; i != 0; )
    {
        list1.push_front( --i );
    }

    std::cout << list1 << '\n';

    List<int> list2;

    list1.extract_half( list2 );

    std::cout << list1 << '\n';
    std::cout << list2 << '\n';

    return 0;
} 

Вывод программы:

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> null

Answer 2

После

Node *secondList = NULL;

Node *headOfSecondList = secondList;

вы больше не изменяете headOfSecondList. При вызове

printLinkedList(headOfSecondList); // => printLinkedList(NULL);

все равно будет NULL Но у вас есть еще одна ошибка в функции копирования:

while (count<=lengthoflist / 2)
{
    Node *temproary = new Node();
    temproary->data=head->data;  
    temproary->next=NULL;        
    secondList=temproary;         // assign secondList 
    secondList=secondList->next;  // secondList->next is temporary->next is NULL!!
    head=head->next;
    count++;
}

Здесь вы создаете группу узлов, у которых все есть next из NULL. Вы действительно теряете память здесь. secondList устанавливается в NULL в конце каждой итерации, и когда temporary выходит из области видимости, у вас не остается указателей на выделенную память.

Следующее должно работать

// Build first node
Node *secondList = new Node();
secondList->data = head->data;
// advance by one
head = head->next;

// Now this points to the real head instead of NULL
Node *headOfSecondList = secondList;

int count=1;

while (count<=lengthoflist / 2 - 1 ) // -1 since we already handled the head above
{
    Node *temproary = new Node();  // new node
    temproary->data = head->data;  // set data
    temproary->next = NULL;        // we have no next yet
    secondList->next = temproary;  // append temporary to secondList
    secondList = secondList->next; //advance secondList
    head = head->next;             // advance head
    count++;
}

printLinkedList(headOfSecondList);

Я пропустил некоторые проверки здесь, но я надеюсь, что концепция basi c теперь более понятна.