时间戳

首页 > 解决方案 > 从另一个链表创建链表时出错？

c++ - 从另一个链表创建链表时出错？

问题描述

我正在从另一个链表创建一个链表。但是第二个链表没有形成，运行程序时出现内存泄漏消息。

这是令人不安的代码部分-


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() 函数完美地打印出传入列表，但不是第二个链表。

标签： c++algorithmdata-structureslinked-listsingly-linked-list

解决方案

如果我理解正确，该函数会尝试从现有列表的前半部分节点构建一个新列表。

如果是这样，则无需计算源列表中的节点数。这是低效的。

您声明了具有返回类型的函数Node *。

Node *rearrangeLinkedList(Node *head );

但该函数不返回任何内容。

在函数内，变量headOfSecondList被设置一次为 nullptr 并且永远不会改变。

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

在 while 循环中，新节点不会链接在列表中。变量总是被改变secondList并且它的数据成员 next 总是被设置为 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

推荐阅读