链表"append if not present"的递归实现

Question

public bool add(int e)
    {
        if(head == null)
        {
            Node n = new Node 
            {
                element = e
            };
            head = n;
            return true;
        }
        Node t = head;
        if(t.next == null)
        {
            if(t.element == e)
            { return false; }
            Node n = new Node
            {
                element = e
            };
            t.next = n;
            return true;
        }
        t = t.next;
        this.add(e);
        return true;
    }

这是在集合中添加新节点的代码。不允许重复值。有一个名为 Set 的主类和一个名为 Nodes 的内部类。我知道节点 t = 头; 是否会产生问题，无论如何都要使它递归？即使传递额外的可选参数也无济于事。

Answer 1

如果我

正确理解了你的问题，要使其递归，你需要将其拆分为两个函数，一个用于处理head == null情况的公共函数，一个用于处理n.next == null并且是递归的私有函数。

public bool add(int e)
{
    if (head == null)
    {
        head = new Node { element = e };
        return true;
    }
    return add(head, e);
}
private bool add(Node n, int e) {
    if (n.element == e)
        return false;
    if (n.next == null) {
        n.next = new Node { element = e };
        return true;
    }
    return add(n.next, e);
}

但是，我建议改为做一些类似于以下内容的事情，在一个函数中完成所有操作：

public bool add(int e)
{
    if (head == null)
    {
        head = new Node { element = e };
        return true;
    }
    if (head.element == e)
        return false;
    Node n = head;
    while (n.next != null) {
        if (n.element == e)
            return false;
        n = n.next;
    }
    n.next = new Node { element = e };
    return true;
}