17370845950

本文介绍了如何在 Kotlin 中实现一个函数，该函数接收两个双向循环链表 list1 和 list2，以及一个比较器 cmp。函数的功能是找出两个链表的交集，并从原链表中删除交集元素。最终返回一个新的链表，该链表包含两个输入链表的交集元素，且不包含重复元素，并保留元素的原始顺序。

问题描述

给定两个双向循环链表 list1 和 list2，它们都已按照比较器 cmp 升序排序。目标是找到这两个链表的交集，并从 list1 和 list2 中删除这些交集元素。最终返回一个非循环的双向链表，其中包含交集元素，且元素已排序，不包含重复项。要求尽可能复用 list1 或 list2 的节点，避免创建过多的新节点。

实现思路

1. 遍历 list1: 外层循环遍历 list1 的每个节点。
2. 遍历 list2: 内层循环遍历 list2 的每个节点。
3. 比较节点值: 使用比较器 cmp 比较 list1 和 list2 当前节点的值。
4. 找到交集: 如果两个节点的值相等，则找到了一个交集元素。
5. 删除节点: 从 list1 和 list2 中删除该交集元素对应的节点。
6. 添加到结果链表: 将删除的节点添加到新的结果链表中。
7. 构建结果链表: 确保结果链表是非循环的，并且元素已排序，不包含重复项。
8. 复用节点: 尽可能复用 list1 或 list2 的节点。

代码实现

class Node {
    var previous: Node? = null
    var next: Node? = null
    var value: E? = null
}

fun  intersection(list1: Node, list2: Node, cmp: Comparator): Node? {
    var list: Node? = null
    var temp = list1
    var temp2 = list2
    var count = 0
    var head : Node? = null

    // 外层循环遍历 list1
    while (temp.next?.value != null){
        temp = temp.next!!

        // 内层循环遍历 list2
        var temp2Current = temp2 // 保存 list2 的起始位置，每次外层循环开始时重置
        while(temp2Current.next?.value !=null){
            temp2Current = temp2Current.next!!
            if(cmp.compare(temp.value,temp2Current.value)==0 ){
                // 找到交集元素，删除 list1 中的节点
                var novo = deleteNode(temp)

                // 将删除的节点添加到结果链表
                if (list != null){
                    novo.previous = list
                    list.next = novo
                }
                list = novo

                count ++
                if(count==1){
                    list.previous = null
                    head = list
                }

                // 删除 list2 中的节点
                deleteNode(temp2Current)
                break; // 找到一个交集元素后，跳出内层循环
            }
        }
        temp2 = list2 // 每次外层循环开始时重置 temp2 为 list2 的起始位置

    }

    return head
}

fun  deleteNode(node : Node): Node{

    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
}

代码解释

• intersection(list1, list2, cmp) 函数:

  • 初始化结果链表的头 head 和尾 list 为 null。
  • 使用 temp 遍历 list1，使用 temp2 遍历 list2。
  • 当找到相等的节点时，调用 deleteNode 从 list1 和 list2 中删除该节点。
  • 将删除的节点添加到结果链表中。
  • 返回结果链表的头 head。

• deleteNode(node) 函数:

  • 找到要删除节点的前一个节点 prev 和后一个节点 next。
  • 将 prev 的 next 指针指向 next，将 next 的 previous 指针指向 prev。
  • 返回被删除的节点。

注意事项

• 该实现假设输入链表 list1 和 list2 是循环链表，且都有哨兵节点。哨兵节点的 value 属性为 null。
• deleteNode 函数在删除节点后，需要更新相邻节点的 next 和 previous 指针，以保持链表的完整性。
• 代码中包含重复元素消除的逻辑，确保结果链表中的元素不重复。
• 需要谨慎处理空指针情况，例如当 prev 或 next 为 null 时。
• 在遍历 list2 时，每次外层循环开始时需要重置 temp2 为 list2 的起始位置，否则会因为内层循环的移动导致遍历不完整。

总结

本文提供了一个在 Kotlin 中实现有序链表求交集并删除元素的示例代码。该代码通过遍历两个链表，比较节点值，删除交集元素，并将删除的节点添加到新的结果链表中，最终返回一个包含交集元素的非循环链表。该实现复用了原链表的节点，避免了创建过多的新节点，提高了效率。 请注意根据你的实际情况修改代码，例如处理非循环链表或没有哨兵节点的情况。