所以我想知道什么是链表中的虚拟头 / 虚拟节点。有人可以告诉我定义,给我一个例子吗?
虚拟节点更像是一个黑客,通常用于避免为边缘情况编写额外的代码。
考虑以下在链表中的尾部插入的情况:
void insertAtTail(Node oldTail, int i){
Node newTail = new Node(i);
oldTail.next = newTail;
return newTail;
}
当 oldTail 不为 null 时,这工作正常。但是想象一下我们试图在空列表上执行 insertAtTail () 的场景。如果节点为 null,上面写的代码将不起作用。因此,我们必须处理检查 oldTail 是否为 null 的边缘情况:
Node insertAtTail(Node oldTail, int i){
Node newTail = new Node(i);
if(oldTail == null) {return newTail;}
oldTail.next = newTail;
return newTail;
}
在这样的场景中,虚拟节点会派上用场。想象一下,我有一个虚拟节点,如下所示:
Node dummy = new Node(0);
现在我们将这个虚拟节点传递给调用函数:
insertAtTail(dummy, 5);
当一个虚拟节点被传递给调用函数时,你会发现这里不需要检查虚拟节点是否为 null。因此,我们可以跳过空节点的检查:
Node insertAtTail(Node dummy, int i){
Node newTail = new Node(i);
dummy.next = newTail;
return newTail;
}
正如你所看到的,我已经删除了检查空这里。
当链表的头不指向任何节点时,您将创建一个从该头指向的虚拟头(节点)。这样,您将始终能够到达例如head.val
或head.next
,而无需执行任何额外的空检查。
本站系公益性非盈利分享网址,本文来自用户投稿,不代表边看边学立场,如若转载,请注明出处
评论列表(32条)