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

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 *secondList = NULL;

Node *headOfSecondList = secondList;

您不再修改 headOfSecondList。当你调用

时它仍然是NULL

printLinkedList(headOfSecondList); // => printLinkedList(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);

我在这里跳过了一些验证，但我希望现在基本概念更清楚了。

Answer 2

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

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

您声明的函数具有 return 类型 Node *。

Node *rearrangeLinkedList(Node *head );

但是函数return什么都没有。

在函数中，变量 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;
}

为了在不计算源列表中的节点数的情况下演示该方法，正如我已经指出的那样效率低下，这里是一个带有 class 模板列表的演示程序。

#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

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

Error in creating a linked list from another linked list?

c++

algorithm

linked-list

data-structures

singly-linked-list