Вычитание между двумя узлами

Question

Мне нужно написать код, чтобы решить эту проблему:

-Считать вычитание между двумя узлами p и q, где вычитание p - q - это список, который содержит все элементы, которые появляются вp, а не q, зная, что p и q - упорядоченные списки.

Я попытался написать код, и я знаю, что он не может работать ... Можете ли вы помочь мне решить эту проблему?большое спасибо!

 class Node{
    public int elem;
    public Node next;

    public Node(int elem, Node next){
        this.elem = elem;
        this.next = next;
    }

}

 public class Main{
     public static Node diff(Node p, Node q){
            if( p.elem == q.elem )
                return diff(p.next, q.next);
            else if(p.elem < q.elem){
                return new Node (p.elem, diff(p.next, q.next));
            else
                return new Node(p.elem, diff(p.next, q.next));
        }
 public static void main(String[] args){
 //.......
 }
 }

Answer 1

Ваша рекурсия никогда не заканчивается, поскольку каждый оператор return в вашем методе рекурсии вызывает сам себя, что приведет ваш код к переполнению стека.

Чтобы решить эту проблему, вы должны разложить проблему.

Прежде всего, давайте найдем базовые случаи. Это случаи, когда рекурсия заканчивается, и есть две проблемы для вашей проблемы:

• Если p == null, т. Е. Если в связанном списке больше нет элементов, значит, работа выполнена, больше нечего добавить к вашему связанному списку результатов.

if(p == null)
{
    return null;
}

• Если q == null, то вы должны добавить все оставшиеся элементы в свой связанный список, то есть сам узел p.

if(q == null) 
{
    return p;
}

Существует еще 3 возможных случая рекурсии:

• Если p.elem == q.elem, то узел не должен быть добавлен, и мы должны перейти к следующему узлу для каждого связанного списка. Поскольку список упорядочен, этот узел не может быть полезен позже.

if(p.elem == q.elem)
{
    return diff(p.next, q.next);
}

• Если p.elem > q.elem, то узел может быть полезен, но мы пока не знаем. Следующие узлы второго связанного списка могут быть равны, поэтому мы просто перейдем к следующему узлу для второго связанного списка.

if (p.elem > q.elem) 
{
    return diff(p, q.next);
}

• Остается только один случай, если p.elem < q.elem. Вот и все, мы уверены, что этот узел отсутствует во втором связанном списке, поэтому мы добавляем новый узел в наш результат.

return new Node(p.elem, diff(p.next, q);

Обратите внимание, что вы не нуждаетесь в выписке else в каждом случае, поскольку в каждом из ваших случаев есть возврат.

Надеюсь, это поможет!