本教程将指导你如何在 Kotlin 中实现一个函数，该函数接收两个已排序的双向循环链表以及一个比较器作为输入，返回一个新的链表，其中包含两个输入链表的交集元素，并且这些元素会从原始链表中删除。我们将深入探讨链表操作的细节，包括节点的删除和连接，以及如何避免常见的错误，例如在迭代过程中修改链表结构。
fun <E> intersection(list1: Node<E>, list2: Node<E>, cmp: Comparator<E>): Node<E>? {
var list: Node<E>? = null
var temp = list1
var temp2 = list2
var count = 0
var head : Node<E>? = null
while (temp.next?.value != null){
temp = temp.next!!
while(temp2.next?.value !=null){
temp2 = temp2.next!!
if(cmp.compare(temp.value,temp2.value)==0 ){
var novo = deleteNode(temp)
if (list != null){
novo.previous = list
list.next = novo
}
list = novo
count ++
if(count==1){
list.previous = null
head = list
}
deleteNode(temp2)
break;
}
}
temp2 = list2
}
return head
}
fun <E> deleteNode(node : Node<E>): Node<E>{
var prev = node.previous
var next = node.next
while(next!=null && next!!.value == node.value ){ // 删除重复元素
next = next.next
}
if (prev != null) {
prev.next = next
}
if (next != null) {
next.previous = prev
}
return node
}
class Node<E> {
var previous: Node<E>? = null
var next: Node<E>? = null
var value: E? = null
}代码解析：
-
intersection 函数：
- 该函数接收两个双向循环链表 list1 和 list2，以及一个比较器 cmp 作为输入。
- 初始化 list 为 null，用于构建新的交集链表。
- 使用 temp 和 temp2 分别迭代 list1 和 list2。注意，这里假设 list1 和 list2 是带有哨兵节点的循环链表。
- 外层循环遍历 list1，内层循环遍历 list2。
- 如果 cmp.compare(temp.value, temp2.value) == 0，说明找到了一个交集元素。
- 调用 deleteNode 函数从 list1 和 list2 中删除该元素。
- 将删除的节点添加到新的交集链表 list 中。
- count 变量用于记录交集链表的节点数，用于设置头节点的 previous 指针为 null。
- 最后返回交集链表的头节点 head。
-
deleteNode 函数：
- 该函数接收一个要删除的节点 node 作为输入。
- 获取 node 的前驱节点 prev 和后继节点 next。
- 关键步骤： 循环检查 next 节点是否与当前节点值相等，如果相等，则继续向后移动 next 节点，以删除重复元素。
- 更新 prev 和 next 节点的指针，将 node 从链表中移除。
- 返回删除的 node 节点，以便将其添加到交集链表中。
注意事项：
- 循环链表： 该实现假设输入链表是循环链表，并且带有哨兵节点。如果没有哨兵节点，需要修改循环的终止条件。
- 删除重复元素： deleteNode 函数中包含删除重复元素的逻辑。 如果不需要删除重复元素，可以简化该函数。
- 内存管理： 由于代码复用了原始链表的节点，因此不需要额外的内存分配。但需要确保在使用完交集链表后，不再使用原始链表的被删除节点，或者进行适当的内存管理。
- 比较器： 确保提供的比较器 cmp 与链表的排序方式一致。
总结：
这个解决方案提供了一种高效的方法来查找两个排序双向循环链表的交集，并在原始链表中删除交集元素。通过复用原始链表的节点，可以避免额外的内存分配。同时，deleteNode 函数中的重复元素删除逻辑增强了代码的鲁棒性。理解链表操作的细节以及注意事项，可以帮助你更好地应用这个解决方案。
