根据一个具体的单向链表,复制建立一个双向链表,然后输出双向链表
时间: 2024-10-16 17:14:24 浏览: 33
当我们从一个单向链表转换到双向链表时,我们需要为每个节点添加一个前驱指针,以便它可以指向其前一个节点。以下是如何在C++中实现这个过程的一个简单示例:
```cpp
#include <iostream>
// 定义单向链表节点结构体
struct ListNode {
int val;
ListNode* next;
// 新增一个prev指向前一个节点
ListNode* prev = nullptr; // 双向链表特有的属性
};
// 单向链表节点拷贝构造函数和赋值操作符
ListNode::ListNode(int x) : val(x), next(nullptr) {}
ListNode* copyList(ListNode* head) {
if (head == nullptr) {
return nullptr;
}
// 创建新双向链表的头节点
ListNode* newHead = new ListNode(head->val);
ListNode* curr = newHead;
// 遍历原链表并更新节点的前驱指针
ListNode* temp = head;
while (temp != nullptr) {
// 创建新的节点并保存下一个节点
ListNode* newNode = new ListNode(temp->val);
newNode->prev = curr;
curr->next = newNode;
curr = newNode;
// 移动到下一个原链表节点
temp = temp->next;
}
// 返回新链表的头节点
return newHead;
}
// 打印双向链表
void printList(ListNode* head) {
ListNode* curr = head;
while (curr != nullptr) {
std::cout << curr->val << " ";
curr = curr->next;
}
std::cout << std::endl;
}
int main() {
// 假设我们有一个已存在的单向链表 head
ListNode* head = ... // 填充实际的单向链表
// 将单向链表复制到双向链表
ListNode* newHead = copyList(head);
// 输出复制后的双向链表
printList(newHead);
// 清理内存
delete newHead;
while (head != nullptr) {
ListNode* temp = head;
head = head->next;
delete temp;
}
return 0;
}
```
在这个例子中,`copyList` 函数遍历原始单向链表,创建相应的双向链表节点,并连接它们。`printList` 函数用于打印链表中的元素。
阅读全文