从另一个链接列表创建链接列表时出错

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

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

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

您声明了返回类型为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