合并链表中的递归

Question

我开始理解递归，

我已经附加了递归代码来合并两个排序的链接列表，

我的问题是，我知道当第一个或第二个变为空时，'temp‘返回temp->(第一个(或)第二个)的值，但是我无法理解，

例如，如果我有5 -> 10 -> 15 -> 20。

最后一个函数返回15 ->20，然后将其组合为root.next-> temp，但是在这一步之后，当我返回temp时，为什么返回根值。即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. now 您可以再次调用方法sortedLists()，但是使用新的值:根现在是5，第一个是10，第二个是15。我们进入函数并从新的值开始：

1. because of `first.data < second.data`, temp becomes 10, first is now null.
2. and again: we reached another call on `sortedLists()`. We pass the values: `first = null second = 15 root = 10` to the function and go one step deeper.  
    1. as `first` is now zero, `temp.next` will be `second`(15) 
    2. temp looks like this now: 10->15 and we return. (this is the first time, `sortedLists()` terminates!)

​

1. We are now back here and can move on with `root.next = temp;` Remember what temp was in this context? temp was 10 but it has been updated by the function above.  The new `temp` is 10->15, so our `root` looks like: 5->10->15. 
2. Then you print the head of temp, which is 10. This function also terminates.

​

1. 现在我们回到我们的第一个调用，看看会发生什么:在3.3中，我们更新了它的根。根3.3是3的临时值，因为我们调用了sortedLists(first, second, temp) (temp充当根，因为这个函数的最后一个参数是Node root)。
2. 总之:我们的根仍然是0，我们的温度是5->10->15。
3. root.next在这个赋值之后是0->5->10->15。现在，您在您的类中声明的主方法中的根有一个值。
4. 我们返回的温度是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;
        }

我希望这对进入递归有一点帮助。