用c++写一个程序完成在单链表类中增加一个功能copy(L),实现单链表的复制,复制参数L的所有元素。请描述算法的基本设计思想;并根据设计思想,采用程序设计语言描述算法,关键之处请给出简要注释。
时间: 2024-09-28 08:17:39 浏览: 58
在C++中,实现单链表的复制可以使用迭代或递归的方式。这里我们选择迭代的方式来设计这个函数`copy(L)`,因为迭代通常更直观且易于控制。基本的设计思想是:
1. 创建一个新的头结点,用于存储复制后的链表。
2. 遍历源链表`L`,对于每一个节点,创建一个新的节点,并将新节点的`next`指向前一个已经复制好的节点,然后将新的节点添加到结果链表的尾部。
3. 最后返回新链表的头结点。
以下是C++代码实现,关键部分已做了注释:
```cpp
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(nullptr) {} // 构造函数
};
ListNode* copyList(ListNode* L) {
// 创建一个空链表作为结果
ListNode* result = new ListNode(0); // 新链表的头节点
// 当源链表非空时,循环处理
while (L != nullptr) {
// 创建一个新的节点
ListNode* newNode = new ListNode(L->val);
// 将新节点添加到结果链表的尾部
newNode->next = result->next;
result->next = newNode; // 结果链表指向新节点
// 继续遍历源链表
L = L->next;
}
return result->next; // 返回新链表的实际头节点(跳过临时的0值节点)
}
int main() {
// 示例:假设有一个源链表 [1, 2, 3]
ListNode* src = new ListNode(1);
src->next = new ListNode(2);
src->next->next = new ListNode(3);
ListNode* copiedList = copyList(src);
// 打印新链表 [1, 2, 3] (省略了打印实际节点的操作)
while(copiedList != nullptr) {
cout << copiedList->val << " ";
copiedList = copiedList->next;
}
delete copiedList; // 不忘记释放内存
return 0;
}
阅读全文