Рекурсия в объединении связанных списков

Question

Я начинаю понимать рекурсию,

Я прикрепил код рекурсии для объединения двух отсортированных связанных списков,

Моя проблема в том, что я понимаю, что temp возвращает значение temp-> (первая (или) вторая), как только первая или вторая становится нулевой, но я не могу понять тот факт, что

Скажем, например, если у меня 5 -> 10 -> 15 -> 20.

Функция final возвращает 15 -> 20, которая затем комбинируется как root.next-> temp, но после этого шага, когда я возвращаю temp, почему возвращается значение root.то есть 10 -> 15 -> 20, когда я ожидаю, что будет возвращена только температура.

Пожалуйста, найдите код,

 /**
 * 
 */
 *
 *
 */
public class MergeLinkedLists {

    static class Node {

        int data;
        Node next;

        public Node(int value) {
            this.data = value;
        }

    }

    Node root;

        /**
     * @param args
     */

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MergeLinkedLists s1 = new MergeLinkedLists();
        s1.root = new Node(0);
        Node n1 = new Node(10);
        //n1.next = new Node(20);
        //n1.next.next = new Node(30);

        Node n2 = new Node(5);
        n2.next = new Node(15);
        //n2.next.next = new Node(50);

        Node result = sortedLists(n1, n2, s1.root);

        while (result != null) {
            System.out.print(result.data + "--->");
            result = result.next;
        }
    }

    /**
     * @param n1
     * @param n2
      * @param root2
     */
     private static Node sortedLists(Node n1, Node n2, Node root) {
         // TODO Auto-generated method stub

        Node temp = root;

        Node first = n1; // 10 20 30
        Node second = n2; // 5 15 50

        if (first == null) {
            temp.next = second;
            return temp;
        } else if (second == null) {
            temp.next = first;
            return temp;
        }

        else if (first.data < second.data) {
            temp = new Node(first.data);
            first = first.next;
        } else {
            temp = new Node(second.data);
            second = second.next;
        }

        sortedLists(first, second, temp);
        root.next = temp;
        System.out.println("The Temp Data is ::::"+temp.data);
        return temp;

    }

}

Answer 1

Поскольку temp - это , в данном случае корневое значение.Не волнуйтесь, это единственное, что вам нужно понять, чтобы понять саму рекурсию.

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

Помимо этого, давайте посмотрим на ваш код.

Важно отметитьзаключается в том, что всякий раз, когда вы вызываете ваш sortedLists(first, second, temp);, указатель будет входить в него до тех пор, пока функция не завершится (например, когда он вернет temp).Вы будете вызывать эту функцию несколько раз, так как программа продолжит работу, поэтому она углубится в свою собственную функцию.Затем он переносит информацию шаг за шагом до уровня, пока не завершится первый вызов sortedLists(first, second, temp);, и это будет в вашем основном методе Node result = sortedLists(n1, n2, s1.root);

Я постараюсь согласиться с вашим примером:

1. Node result = sortedLists(n1, n2, s1.root);, вызываемый в методе main().Таким образом, корень равен 0, и у вас есть ваши узлы 10 и 5,15.

2. При первом вызове sortedLists() temp становится 5, а second теперь несет 15, потому что first.data > second.data.

3. СЕЙЧАС Вы вызываете метод sortedLists() снова, но с новыми значениями: корень теперь 5, первый остается 10, а второй 15. Мышаг внутри функции и начните с новых значений:

   1. из-за first.data < second.data, temp становится 10, сначала ноль.
   2. и снова:мы позвонили на sortedLists().Мы передаем значения: first = null second = 15 root = 10 в функцию и идем на один шаг глубже.
      1. , поскольку first теперь равно нулю, temp.next будет second (15)
      2. temp теперь выглядит так: 10-> 15, и мы возвращаемся.(это первый раз, когда sortedLists() завершается!)
   3. Теперь мы вернулись сюда и можем перейти к root.next = temp; Помните, какой темп был в этом контексте?Temp был 10, но он был обновлен функцией выше.Новый temp равен 10-> 15, поэтому наш root выглядит следующим образом: 5-> 10-> 15.
   4. Затем вы печатаете заголовок temp, который равен 10. Эта функция также завершается.

4. Теперь мы вернулись к нашему первому вызову и посмотрим, что произойдет: в 3.3 мы обновили его корень.Корнем 3.3 был temp из 3, потому что мы назвали sortedLists(first, second, temp) (temp действует как корень, потому что последний аргумент этой функции - Node root).

5. Подводя итог:Наш корень по-прежнему равен 0, а наш темп 5-> 10-> 15

6. root.next после этого назначения 0-> 5-> 10-> 15.Теперь корень, который вы объявили в своем классе выше метода main, имеет значение.

7. , мы возвращаем temp, равную 5-> 10-> 15, и все готово.

Теперь мы можем продолжить в основном методе, распечатывая результаты.

Чтобы избавиться от ---> при отсутствии result.next, вы можете обработать нулевое значениевот так:

 while (result != null) {
            if (result.next != null)
            System.out.print(result.data + "--->");
            else System.out.println(result.data);
            result = result.next;
        }

Надеюсь, это немного поможет в рекурсии.