给定一个具有以下结构的节点
class Node {
int data,
Node* P1,
Node* p2;
}
我们需要确定节点是否表示循环双向链表或二叉树。 在我看来,我们需要从一个方向开始遍历给定的节点
node = givenNode;
while(node->P1 != null && node->P1 != givenNode)
{
node = node->p1
}
if(node == givenNode) // It means Circular DLL
else if(node == null) // It means Tree
检测到这一点需要 O(n) 的时间。
如果有比这更好的方法,请提出建议。
最佳答案
我建议你可以用这段代码检查它是否是双向链表:
node = givenNode;
if(givenNode->P1 == null || givenNode->P2 == null)
// It can not be double link list (circular)
else if(givenNode->p1->p2 == givenNode || givenNode->p2->p1 == givenNode)
{
//It is a double linked list
}
else
{
It is not a double linked list
}
复杂度为 O(1)
关于algorithm - 是双向链表还是 BST,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12563074/