Реализация связанного списка с использованием фиктивных узлов

Question

Я работаю над проектом, где мне нужно объединить и пересечь два набора. Я использую Связанный список для каждого набора с фиктивными узлами. Вот как я инициализирую свои классы LL

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, не такое же значение, поэтому добраться до следующего
• End

Что вы на самом деле нужно:

• На рассогласования, заранее только список с ниже элемента
• На матч, добавить результат и продвижения как (или для удаления дубликатов, продолжайте движение до тех пор, пока повторяется одно и то же значение)

---

Для объединения, идея очень похожа:

• На рассогласования, добавьте ниже один и заранее список, содержащий нижний элемент
• На матче, добавлять и продвигать оба (или продолжаем двигаться вперед и как когда повторяется одно и то же значение)