java - 在java中递归返回已删除的节点

Question

我使用 C++ 学习了大多数链接数据结构，其中有可用的引用传递，并且递归非常简单。我最近切换到 Java，但我总是对这些结构的递归版本感到困惑。

我想将该节点从列表中删除。但我想返回节点。当我从分支返回已删除的节点时else if，它预计会弄乱列表。但我看不出有什么办法。

public node deleteval (int val){

        node prev = head;

        head = deleteval(head,prev,val);

        return head;
    }

 private node deleteval(node head,node prev, int val){

        if(head == null){

            return null;
        }
        else if (head.value == val){

            prev.next = head.next;
            node deleted = head;
            head = prev;


            return head.next;
        }

        prev = head;
        head.next = deleteval(head.next,prev,val);

        return head;
    }

这不是作业，只是试图理解。感谢您的任何意见。

标签： javarecursionlinked-list

Answer 1

要删除节点，您只需要prev.next = head.next处理root节点的边缘情况。不需要堆栈或任何其他支持的数据结构，您只需更深入地递归到列表中，直到找到值或到达末尾。

private Node root;

public Node deleteVal(int val) {
  return deleteRec(root, null, val);
}

private Node deleteRec(Node head, Node prev, int val) {
  if (head == null) {
    return null;
  } 
  if (head.value == val) {
    if (prev != null) { 
      prev.next = head.next; // deleting non-root node
    } else { 
      root = null; // deleting root node  
    }
    return head;
  }
  return deleteRec(head.next, head, val);
}