删除双链表中指定节点之后的节点(递归地)

zujrkrfu  于 2021-06-29  发布在  Java
关注(0)|答案(1)|浏览(351)

我有一个递归函数,它应该删除双链表中指定节点之后的节点。但是我的方法不是删除任何东西。我在重新排列列表中的值时遇到问题。有什么想法吗?

private void deleteAfterThis(T data, Node headAux) {
    if(headAux == null) {
        return;
    }

    Node deleteAfter = new Node(data);
    Node target = deleteAfter.next;
    if(target == null) {
        return;
    }

    if(deleteAfter.prev == null){
        if(target != tail && target==headAux) {
            deleteAfter.next = target.next;
            target.next.prev = deleteAfter;
            size--;
            deleteAfterThis(data, headAux.next);
        }

        else if(target == tail && target == headAux) {
            deleteAfter.next = null;
            deleteAfter = tail;
            size--;
            return;
        }
    }

    else if(deleteAfter.prev != null) {
        if(target != tail && target == headAux) {
            deleteAfter.next = target.next;
            target.next.prev = deleteAfter;
            size--;
            deleteAfterThis(data, headAux.next);
        }
        else if( target == tail && target == headAux) {
            deleteAfter.next = null;
            deleteAfter = tail;
            size--;
            return;
        }
    }

    deleteAfterThis(data, headAux.next);

}
tmb3ates

tmb3ates1#

我马上看到的一个错误是,您不应该为创建一个全新的节点 deleteAfter . 直观地说,在试图删除一个节点时必须创建一个新节点有意义吗?我假设,即使知道构造器的用途 Node 实际上看起来,它设定了 next 以及 prev 指向节点的指针 null . 因此,您将不断递归更新 headAux 直到它结束 null 不删除任何内容。这似乎是你想要的 deleteAfter 待人处事 headAux.next .
我看到的另一个bug是,您已经复制并粘贴了两次检查逻辑—我建议您逐步检查这两种情况,并验证每个代码块中的逻辑是否应该相同 if 以及 else-if 块(可能不应该)。
进入逻辑,你应该意识到 prev 当前节点( headAux 在你的代码)将是 null 只有 headAuxhead 在名单上。因此,重写 headAux.prev 检查是否 headAux 等于 head 链接列表的。
从实际的删除逻辑来看,在一般情况下对我来说似乎是有意义的(假设 deleteAfternext 的节点 headAux 如上所述)。你在制造 prev 指向被删除节点的 prev 节点和 next 上一个节点的指针(在设置了指针之后,我不太喜欢它,但它可以工作)指向 deleteAfter .
最后,当您实际找到要删除的节点时,可能不应该再次调用递归函数。您已经正确地处理了指针的设置,因此不需要这样做。
我强烈建议您(重新)绘制一个循环链表的示例用例,并在跳转到对edgecase进行编码之前在一张纸上执行删除操作(这里没有全部处理)。您可能应该注意的边缘情况如下:空列表、删除头、删除尾、单节点列表。在您的代码中,似乎您确实尝试过处理头的删除(您必须记住在之后设置头)。在让它起作用之后,让删除在其他情况下起作用应该是轻而易举的事。

相关问题