下面是一个完整的C++实现,用于在双向链表中插入另一个双向链表。这种情况下,我们将实现一个方法来将新链表插入到任意位置。
双向链表节点结构体
首先定义双向链表节点的结构体:
#include <iostream>
struct Node {
int data;
Node* prev;
Node* next;
Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};
双向链表类
接下来,我们定义一个双向链表类,包含基本操作和插入另一个链表的方法:
class DoublyLinkedList {
public:
Node* head;
DoublyLinkedList() : head(nullptr) {}
// 向末尾插入元素
void insertAtEnd(int value) {
Node* newNode = new Node(value);
if (head == nullptr) { // 空链表情况
head = newNode;
} else {
Node* last = head;
while (last->next != nullptr) {
last = last->next;
}
last->next = newNode;
newNode->prev = last;
}
}
// 在指定位置插入新的链表
void insertListAtPosition(DoublyLinkedList& newList, int position) {
if (position == 0) { // 如果要在头部插入整个新链表
if (newList.head != nullptr) {
newList.head->next = head;
if (head != nullptr) {
head->prev = newList.head;
}
head = newList.head;
}
} else {
Node* current = head;
for (int i = 0; i < position - 1 && current != nullptr; ++i) {
current = current->next;
}
if (current == nullptr) { // 超出范围,直接返回
std::cerr << "Position out of bounds. Not inserting the list." << std::endl;
return;
}
// 插入新的列表到当前位置之前
if (newList.head != nullptr) {
Node* tempNext = current->next;
current->next = newList.head;
newList.head->prev = current;
if (tempNext != nullptr) {
tempNext->prev = getTail(newList);
getTail(newList)->next = tempNext;
}
}
}
// 清理新列表的head指针,以避免重复引用。
newList.head = nullptr;
}
// 获取当前列表的尾部节点
Node* getTail(DoublyLinkedList& list) {
Node* tailNode = list.head;
while(tailNode && tailNode->next != nullptr){
tailNode=tailNode->next;
}
return tailNode;
}
void display() const {
Node* temp = head;
while (temp != nullptr) {
std::cout << temp->data << " ";
temp = temp->next;
}
std::cout << std::endl;
}
};
示例程序
最后,在main
函数中演示如何使用这些类和方法:
int main() {
DoublyLinkedList dll1, dll2;
dll1.insertAtEnd(10);
dll1.insertAtEnd(20);
std::cout << "Original List 1: ";
dll1.display();
dll2.insertAtEnd(30);
dll2.insertAtEnd(40);
std::cout << "Original List 2: ";
dll2.display();
// 在dll1的位置1处插入dll2
dll1.insertListAtPosition(dll2, 1);
std::cout << "After inserting List 2 into List 1 at position 1: ";
dll1.display();
return 0;
}
程序说明
DoublyLinkedList
类:管理双向链表及其操作,包括添加元素、显示内容以及在特定位置插入另一条链接。insertAtEnd
方法:用于在当前列表末尾添加元素。insertListAtPosition
方法:接受另一个双向链表并将其插入到当前链表的特定位置。如果该位置为零,则将新列表添加到头部。getTail
方法:获取指定列表的最后一个节点。
通过这个示例,你可以方便地将任意两个双向链表合并。你也可以根据需要扩展功能,例如删除某个节点、查找等。
内容由零声教学AI助手提供,问题来源于学员提问