给定一个双向循环链表和一个关键字,我们需要在链表中搜索关键字,并在找到时给出适当的消息。假设我们有一个具有特定字符的链表,并且我们需要在其中搜索一个元素。所以让我们从下面的链表开始 -
<-> 5 <-> 8 <-> 9 <-> 2 <-> 4 <->
我们将使用4作为寻找给定问题解决方案的关键。双向链表没有固定的头部,所以我们将从任意节点开始,然后将该节点标记为头部,直到我们再次遇到这个头部,我们对链表进行线性搜索,并搜索关键字。
让我们看一些输入输出的场景 -
假设我们有一个双向循环链表,其中有5个节点 <-> 3 <-> 4<-> 5<-> 6<-> 7<->,要查找的元素是6。
Input = <-> 3 <-> 4<-> 5<-> 6<-> 7<-> key=6
Output = Element found
让我们考虑另一种情况,即在双向循环链表中没有要搜索的元素。
Input = <-> 10<->20<->30<->40<->50<-> key=100
Output = Element not found
算法
以下是接近的步骤。
实现一个链表,并通过在链表的每个节点中分配前向节点来传递值。
将节点的前一部分分配给最后一个节点的下一部分。
将节点的每个前一部分分配给节点的下一部分。
将关键元素传递给检查它是否存在于双向循环链表中的关键元素。
如果键存在于双向循环链表中,则返回true。
Else, it returns false.
Example
的中文翻译为:示例
以下是在双向链表中执行搜索操作的C++实现代码:
#</span>include</span> <iostream></span></span>
#</span>include</span> <vector></span></span>
using</span> namespace</span> std;</span>
class</span> Node</span> {</span>
public</span>:</span>
int</span> val;</span>
Node *</span>left,</span> *</span>right;</span>
Node</span>(</span>int</span> val)</span> {</span>
this</span>-></span>val =</span> val;</span>
}</span>
}</span>;</span>
bool</span> solve</span>(</span>Node*</span> root,</span> int</span> key)</span> {</span>
Node*</span> copy =</span> root;</span>
do</span> {</span>
if</span>(</span>copy-></span>val ==</span> key)</span> return</span> true</span>;</span>
copy =</span> copy-></span>right;</span>
}</span>while</span>(</span>copy!=</span>root)</span>;</span>
return</span> false</span>;</span>
}</span>
int</span> main</span>(</span>)</span> {</span>
// assigning the forward node in each node of the linked list</span>
Node*</span> phead =</span> new</span> Node</span>(</span>5</span>)</span>;</span>
phead-></span>right =</span> new</span> Node</span>(</span>8</span>)</span>;</span>
phead-></span>right-></span>right =</span> new</span> Node</span>(</span>9</span>)</span>;</span>
phead-></span>right-></span>right-></span>right =</span> new</span> Node</span>(</span>2</span>)</span>;</span>
phead-></span>right-></span>right-></span>right-></span>right =</span> new</span> Node</span>(</span>4</span>)</span>;</span>
phead-></span>right-></span>right-></span>right-></span>right-></span>right =</span> phead;</span>
// assignment of the previous node in each node in the linked list</span>
// assigning the previous of the head to the last element</span>
phead-></span>left =</span> phead-></span>right-></span>right-></span>right-></span>right;</span>
// assigning the left node in each node of the linked list</span>
phead-></span>right-></span>left =</span> phead;</span>
phead-></span>right-></span>right-></span>left =</span> phead-></span>right;</span>
phead-></span>right-></span>right-></span>right-></span>left =</span> phead-></span>right-></span>right;</span>
phead-></span>right-></span>right-></span>right-></span>right-></span>left =</span> phead-></span>right-></span>right-></span>right;</span>
if</span>(</span>solve</span>(</span>phead,</span> 4</span>)</span>)</span> cout <<</span> "Element present"</span>;</span> else</span> cout <<</span> "Element not present"</span>;</span>
return</span> 0</span>;</span>
}</span>
Output
Element present
Explanation
的中文翻译为:解释
关键字4存在于双向链表中。
结论
在一个双向循环链表中,我们可以从任何位置开始,因为没有固定的头部和尾部。在上述方法中,我们有一个“头部”,它是一个伪头部,我们从这里开始搜索。上述算法的时间复杂度是O(n),因为是线性搜索。