将节点插入链表的末尾

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

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;
}

---

递归解决方案通常必须遵守这些规则：

它必须区分一般情况和基本情况。 然后，它必须包含一些类型的代码分叉（通常是一个if ）到两个代码块：基本块和通用块。

基块必须返回一个立即响应（不递归）。

通用块必须重新调用相同的函数（递归），但不能使用相同的参数值（这将产生无限递归），但是具有前向基本大小写的值。

在corse中，这是一个简单的递归模型，实际上它可能更复杂（不止一个基本情况，两个函数之间的递归等）。

如果我们根据这些规则在理论上分析您的建议，我们可以看到它满足所有这些规则。

---

我会稍微深入一些，并删除多个退出点。 这使您可以推理列表中的效果以及返回哪个节点mut。

Node appendRecursive(Node head, int data) {
    // By default return the same list we were given.
    Node list = head;
    if (list == null) {
        // At end of list or list is empty.
        list = new Node();
        list.data = data;
    } else {
        // Recurse.
        head.next = appendRecursive(head.next, data);
    }
    return list;
}

就推理而言，你通常需要使用归纳。

如果列表为空（ list == null ），则创建一个新节点并成为您的列表。

如果列表不为空，则新列表必须是附加了新数据的列表。

鉴于上述情况，可以推断在所有情况下，这将正确运行，因为列表为空或不是。

使用列表上的递归通常被认为是低效和笨重的，因为迭代算法更适合线性结构。 更好的练习是编写自己的Tree结构，因为树可以很好地适应递归算法。 你会发现在树上递归地执行所需的函数通常要容易得多，也更加优雅。

static class Tree {

    Node head = null;

    class Node {

        Node left;
        Node right;
        int data;

        private Node(int data) {
            this.data = data;
        }
    }

    void insert(int data) {
        head = insert(head, data);
    }

    private Node insert(Node node, int data) {
        if (node == null) {
            // Empty tree becomes just the node.
            return new Node(data);
        } else {
            // Pick the correct branch to add this data to.
            if (data < node.data) {
                node.left = insert(node.left, data);
            } else {
                node.right = insert(node.right, data);
            }
        }
        return node;
    }

    private CharSequence toString(Node n) {
        StringBuilder s = new StringBuilder();
        if (n != null) {
            // First print the tree on the left.
            if (n.left != null) {
                s.append(toString(n.left)).append(",");
            }
            // Then the data in this node.
            s.append(n.data);
            // Then the tree on the right.
            if (n.right != null) {
                s.append(",").append(toString(n.right));
            }
        }
        return s;
    }

    @Override
    public String toString() {
        // Even toString is recursive.
        StringBuilder s = new StringBuilder("{");
        s.append(toString(head));
        return s.append("}").toString();
    }
}

public void test() {
    Tree tree = new Tree();
    for (int i : new int[]{6, 5, 4, 3, 2, 1}) {
        tree.insert(i);
    }
    System.out.println(tree);
}

请注意，判断在toString方法中添加“，”的方式非常简单 - 打印列表时出现一个臭名昭着的严重问题。

---

Node Insert(Node head,int data) {
    if (head == null) {
        head  = new Node();
        head.data = data;
    }
    else{
    head.next = Insert(head.next, data);
    }
    return head;
}

假设你有5,3,2,1，并且你想添加4然后： - insert（node（5），int 4）

if( node(5) == null ) no then head.next = node(5).next是node(3)并调用Insert(node(3),4)

if( node(3) == null ) no then head.next = node(3).next是node(2)并调用Insert(node(2),4)

if( node(2) == null ) no then head.next = node(2).next ，它是node(1)并调用Insert(node(1),4)

if( node(1) == null )没有那么head.next = node(1).next是null “ 因为有后没有元素 node(1)和呼叫Insert(node(1).next,4)

(node(1).next) == null yes then set head = new node (); 并设置数据head = new node (); 在最后回头

链接地址: http://www.djcxy.com/p/29047.html

上一篇: Insert node at the end of linked list

下一篇: Mixed mode assembly is built against version ‘v2.0.50727′ of the runtime