两单链表的差集java

### Java中实现两个单链表的差集

为了实现在Java中计算两个单链表的差集，可以采用遍历的方法来比较两个列表中的元素。对于每一个存在于第一个单链表（设为`listA`）中的节点，在第二个单链表（设为`listB`）里查找是否存在相同的值；如果不存在，则保留此节点作为差集中的一部分。

下面是一个具体的算法描述以及相应的代码实现：

#### 定义单链表的数据结构
首先定义一个简单的单链表节点类 `ListNode` 和辅助方法用于创建测试用例[^3]。

class ListNode {
    int val;
    ListNode next;

    public ListNode(int x) {
        this.val = x;
        this.next = null;
    }
}

#### 实现差集功能
接着编写函数 `difference()` 来获取两个单链表之间的差集，并将结果存入原单链表 A 中[^2]。

public static void difference(ListNode headA, ListNode headB) {
    // 使用HashSet提高查询效率
    Set<Integer> setB = new HashSet<>();
    
    // 将headB的所有元素加入到setB中
    while (headB != null){
        setB.add(headB.val);
        headB = headB.next;
    }

    // 创建虚拟头结点简化边界条件处理
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = headA;
    ListNode prev = dummyHead; 

    // 遍历headA移除出现在setB里的元素
    while (headA != null){
        if(setB.contains(headA.val)){
            prev.next = headA.next;  // 删除当前节点
        }else{
            prev = headA;           // 移动prev指针
        }
        headA = headA.next;
    }
}

上述代码通过引入哈希集合提高了查找速度从而优化了性能表现。这里假设输入的是无重复项的有序或无序单向链表。需要注意的是，这种方法的空间复杂度不是严格意义上的 O(1)，因为额外使用了一个哈希表来存储 B 列表的信息。要达到真正的 O(1) 空间复杂度需求，则可能需要更复杂的逻辑设计，比如先对其中一个链表进行反转再逐个对比删除等操作。