使用虚拟节点的链表实现

Question

我正在做一个项目，我必须将两个集合并集和相交。我正在为每个带有虚拟节点的集合使用链表。这就是我初始化 Sets LL class

的方式

public Set() {
 top = new Node(Integer.MIN_VALUE, new Node(Integer.MAX_VALUE, null) );
} //end Set

这就是我插入项目的方式。

public void insert(int item) {
 Node prev = top;
 Node curr = top.next;

 while( curr.item < item ) {
  prev = curr;
  curr = curr.next;
 }
 prev.next = new Node( item, curr);
 size++;
} // insert

现在我发现很难得到两组的并集或交集。这就是我对交叉口的想法。

public Set intersection( Set setB ) {
 Set setC = new Set ();
 //loop over both sets and if both have same value add it otherwise 
 // get to the next node in both sets.

我的问题是，我的交集伪代码在逻辑上是否正确？不过，我的联合伪代码很可笑。谁能指导我解决这个问题？

Answer 1

对于这个简单的输入，您的想法将失败：

1  2
2  3

你的想法：

//loop over both sets and if both have same value add it otherwise 
// get to the next node in both sets.

第一次迭代 - 我们有 1 和 2，不同的值，所以我们在两个集合中进行下一次迭代
第二次迭代 - 我们有 2 和 3，不同的值，所以进入下一个
结束

您实际需要的是：

不匹配时，仅推进具有 lower 元素
在匹配时，添加到结果并推进两者（或删除重复项，只要重复相同的值就继续推进两者）

对于union，思路很相似：

不匹配时，添加较低的元素并推进包含较低元素的列表
在匹配时，添加并推进两者（或者只要重复相同的值就继续推进两者）

使用虚拟节点的链表实现

Linked List Implementation using dummy nodes

java

linked-list

set

set-intersection

set-union