使用链表迭代器实现链表的合并
时间: 2024-10-08 14:23:24 浏览: 15
使用链表迭代器来合并链表是一种常见的高级技巧,它允许我们在不需要暴露底层链表结构的情况下进行操作。基本思路是定义一个迭代器类,该类包含对链表节点的操作,如移动到下一个节点、获取节点值等。然后,我们可以为每个链表创建一个迭代器,并使用它们在循环中逐个比较节点的值,将较小的节点链接到结果链表上。
假设我们有两个单向链表 `list1` 和 `list2`,我们可以定义一个 `LinkedListIterator` 类:
```cpp
class LinkedListIterator {
private:
ListNode* current;
public:
LinkedListIterator(ListNode* node) : current(node) {}
// 指向下个节点
void next() {
current = current->next;
}
// 返回当前节点的值
int value() const {
return current->value;
}
// 判断是否还有下一个节点
bool hasNext() const {
return current != nullptr;
}
};
// 合并两个链表
ListNode* mergeLinkedLists(ListNode* list1, ListNode* list2) {
LinkedListIterator iter1(list1), iter2(list2);
ListNode* resultHead = nullptr;
ListNode* currentResult = nullptr;
while (iter1.hasNext() && iter2.hasNext()) {
if (iter1.value() < iter2.value()) {
if (!resultHead) {
resultHead = new ListNode(iter1.value());
currentResult = resultHead;
} else {
currentResult->next = new ListNode(iter1.value());
currentResult = currentResult->next;
}
iter1.next();
} else {
if (!resultHead) {
resultHead = new ListNode(iter2.value());
currentResult = resultHead;
} else {
currentResult->next = new ListNode(iter2.value());
currentResult = currentResult->next;
}
iter2.next();
}
}
// 将剩余的部分连接到结果链表末尾
while (iter1.hasNext()) {
currentResult->next = new ListNode(iter1.value());
currentResult = currentResult->next;
iter1.next();
}
while (iter2.hasNext()) {
currentResult->next = new ListNode(iter2.value());
currentResult = currentResult->next;
iter2.next();
}
return resultHead;
}
```
在这个例子中,`mergeLinkedLists` 函数接受两个链表的头结点作为参数,通过 `LinkedListIterator` 来比较和链接节点,实现了链表的合并。
阅读全文