java 使用递归在链表中添加尾节点&不使用节点参数

bogh5gae 于 2023-03-21 发布在 Java

关注(0)|答案(2)|浏览(120)

我有以下方法

public void insertTailNode(T data) {
        if (this.head == null) {
            Node<T> temp = new Node<T>(data, null);
            this.head = temp;
            this.size++;
        } else if (this.head.getNext() == null) {
            Node<T> temp = new Node<T>(data, this.head);
            this.head = temp;
            this.size++;
        } else {
            this.head = head.getNext();
            insertTailNode(data);
        }
    }

如何使用递归添加尾节点？
我尝试在头节点上使用构造函数，但很明显，每次调用都会重置回第一个节点。

Java

来源：https://stackoverflow.com/questions/75792674/append-tail-node-in-linked-list-with-recursion-no-node-param

2条答案

按热度按时间

mkshixfv1#

你不能在没有节点param/variable的情况下使用recursion * 和 * 来实现它...
我们可以反复进行：

public void insertTailNode(T data) {
  if (head == null) { // empty list!! (size == 0)
    head = new Node<>(data, null); // alternatively: insertHeadNode(data);
  } else { // list not empty!! we have to "iterate" ...
    Node cursor = head; // ...start with head...
    // ...until cursor.next == null:
    while (cursor.next != null) {
      cursor = cursor.next; // that easy!
    } // done! cursor.next MUST be null, cursor is last element (whether it was 1 or 100 elements;)
    // insert new node (after cursor):
    cursor.next = new Node(data, null);
  } // end-else
  // we inserted one node in any case (disregarding exceptions), so:
  size++;
}

“递归地”（但不是没有参数/变量！），它可能看起来像：

public void insertTailNode(T data) {
  if (head == null) { // empty list!! (size == 0)
    head = new Node<>(data, null); // alternatively: insertHeadNode(data);
  } else { // list not empty!! we have to "recurse" ...
    insertTailRec(head, data); //.. starting with head! (head != null;)
  }
  // finally:
  size++;
}

与：

private void insertTailRec(Node current, T data) {
  // assert(current != null); //!!
  if (current.next == null) {// we found the tail/terminate recursion
    current.next = new Node<>(data, null);
  } else { // current.next != null (!!!), recurse:
    insertTailRec(current.next, data);
  }
}

赞(0）回复(0）举报 2023-03-21

798qvoo82#

已经有了一个充分的答案。
您的代码是错误的，因为它试图使用head作为变量来指向最后一个节点。
事实上，递归需要一个额外的状态/参数来进行递归调用。因此，人们经常看到一个公共非递归方法调用一个带有额外状态的递归方法。这里它将是头节点。

赞(0）回复(0）举报 2023-03-21