java - 在链表末尾插入节点

Question

对于这类问题，有一个简单的迭代解决方案。

Node Insert(Node head,int data) {
    Node newNode = new Node();
    newNode.data = data;
    if (head == null) {
        return newNode;
    }
    Node current = head; 
    while (current.next != null) {
        current = current.next;
    }
    current.next = newNode;
    return head;
}

它工作得很好。但我想学习递归并以这种视角看待事物。因此我想出了下面的解决方案，它看起来很优雅，但我不得不承认这只是直觉并且给定的代码有效。我想开发一个处理递归的心智模型，或者至少以某种方式来验证我的代码是否可以正常工作。如何从理论上验证以下解决方案是否有效。

递归版本

Node Insert(Node head,int data) {
    // Base case.
    if (head == null) {
        Node newNode = new Node();
        newNode.data = data;
        return newNode;
    }
    // Smaller problem instance.
    head.next = Insert(head.next, data);
    return head;
}

Answer 1

递归解决方案通常必须遵守以下规则:

1. 它必须区分一般 情况和基本 情况。然后，它必须包含某种类型的代码 fork (通常是一个 if)到两个代码块:基本 block 和通用 block 。
2. 基础 block 必须立即返回响应(非递归)。
3. 通用 block 必须(递归地)重新调用相同的函数，但不是使用相同的参数值(这将产生无限递归)，而是使用前进到基础的值案例。

当然，这是一个简单的递归模型，在实践中可能会更复杂(不止一个基本情况，两个函数之间的递归等)。

如果我们根据这些规则从理论上分析您的提案，我们可以看到它符合所有这些规则。