递归复制链表（Java）

Question

一个漫长的夜晚结束后，我在递归复制链表时遇到了麻烦，我可以用一个简单的迭代方法来实现，但是当我尝试用递归设置它时，我遇到了堆栈溢出错误。然而，这在概念上对我来说是有意义的。谁能把我引向正确的方向？这就是我到目前为止所做的：

public LinkedList<E> createCopyRecursive(Node<E> aNode) {
    LinkedList<E> copyList = new LinkedList<E>();
    copyList.myStart = myStart;

    if (copyList.size() == 0) {
        aNode = myStart.getLink();
    }

    if (aNode.getLink() == null) {
        return copyList;
    }
    else {
        copyList.add(aNode.getValue());
        return createCopyRecursive(aNode.getLink());
    }
}

Answer 1

您可以只担心头节点，而不是传递整个linkedlist对象

调用递归方法copy()

Node<Integer> copiedHead = copy(head);    

递归方法copy，接受head节点并返回复制的head节点

private static Node<Integer> copy(Node<Integer> head) {
    if(head == null){
        return null;
    }   
    return new Node<>(head.getData(), copy(head.getNext()));            
}

Answer 2

如果您想使用递归方法复制链接列表，我认为您应该首先在另一个调用createCopyRecursive（）的方法中初始化copyList

createCopy(Node<E> aNode) {
   LinkedList<E> copyList = new LinkedList<E>();
   createCopyRecursive(aNode, copyList) {
      ....
   }
}

Answer 3

我认为可以这么简单：

private LinkedList<E> copyRecursive(final Node<E> node, final LinkedList<E> accumulator) {
                if (node == null) {
                    // all nodes traversed, return the result.
                    return accumulator;
                }
                // add current node to the copy list that is under construction.
                accumulator.add(node.getElement());
                // recursive call to copy the rest of the nodes to the copy list and return it when finished.
                return copyRecursive(node.getNext(), accumulator);
            }

首先创建一个空的新链表，其中将包含副本，然后逐节点递归地将副本复制到其中。您也不能像这样将累加器传递给它：

private LinkedList<E> copyRecursive(final Node<E> node) {
                    if (node == null) {
                        return new LinkedList<>();
                    }
                    final LinkedList<E> accumulator = copyRecursive(node.getNext());
                    accumulator.add(node.getElement());
                    return accumulator;
                }

但这将颠倒列表中节点的顺序

下面是一个使用递归复制和递归反转的完整工作示例：

public class RecursiveCopyTest {
    public static void main(String[] args) {
        final LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("first");
        linkedList.add("next");
        linkedList.add("last");
        System.out.println(linkedList);
        System.out.println(linkedList.copyRecursive());
        System.out.println(linkedList.reverse());
   }

private static class LinkedList<E> {

    private Node<E> first;

    public LinkedList() {
        first = null;
    }

    public LinkedList<E> copyRecursive() {
        return copyRecursive(first, new LinkedList<E>());
    }

    public LinkedList<E> reverse() {
        return reverse(first);
    }

    public void add(E element) {
        final Node<E> node = new Node<>(element);
        if (first == null) {
            first = node;
        } else {
            Node<E> current = first;
            while (current.getNext() != null) {
                current = current.getNext();
            }
            current.setNext(node);
        }

    }

    private LinkedList<E> reverse(final Node<E> node) {
        if (node == null) {
            return new LinkedList<>();
        }
        final LinkedList<E> accumulator = reverse(node.getNext());
        accumulator.add(node.getElement());
        return accumulator;
    }

    private LinkedList<E> copyRecursive(final Node<E> node, final LinkedList<E> accumulator) {
            if (node == null) {
                return accumulator;
            }
            accumulator.add(node.getElement());
            return copyRecursive(node.getNext(), accumulator);
        }

        @Override
        public String toString() {
            final StringBuilder stringBuilder = new StringBuilder();
            Node current = first;
            while (current != null) {
                stringBuilder.append(current.getElement().toString()).
                        append(" -> ");
                current = current.getNext();
            }
            stringBuilder.append(" _ ");
            return stringBuilder.toString();
        }

        private static final class Node<E> {
            private final E element;
            private Node<E> next;

            public Node(final E element) {
                this.element = element;
            }

            public E getElement() {
                return element;
            }

            public void setNext(final Node<E> next) {
                this.next = next;
            }

            public Node<E> getNext() {
                return next;
            }
        }
    }
}

Answer 4

每次递归到该方法时，都会创建一个新的LinkedList

我怀疑您希望在方法之外实例化它，每次通过时传入并添加它