使用 C++ 在链表中搜索元素

要在链表中搜索一个元素，我们必须遍历整个列表，将每个节点与所需数据进行比较，并持续搜索直到找到匹配项。由于链表不提供随机访问，因此我们必须从第一个节点开始搜索。

给定一个整数链表和一个整数键。我们需要找到这个键是否存在于我们的链表中。我们可以在链表中进行简单的线性搜索并找到键。如果存在，则返回“是”；否则，返回“否”。

让我们看看一些输入-输出场景 -

我们创建了一个列表，我们需要找到元素是否在该列表中，并根据提供的键（3）获得相应的输出 -

Input Data: [ 10, 4, 5, 4, 10, 1, 3, 5]
Output: Yes

让我们考虑另一种场景，其中提供的键为 5 -

Input Data: [ 1, 4, 9, 4, 10, 1, 3, 6]
Output: No

算法（步骤）

以下是执行所需任务需要遵循的算法/步骤 -

• 将头部设置为 null。

• 向链表中添加一些项

• 获取用户要搜索的项目的输入。

• 从头到尾线性遍历链表，直到到达 null 节点。

• 检查每个节点以查看数据值是否与要搜索的项目匹配。

• 返回找到数据的节点的索引。如果未找到，则转到下一个节点。

示例

例如，让我们有一个这样的链表：“52->4651->42->5->12587->874->8->null”，其键为 12587。下面给出了实现该示例的 C++ 程序 -

#include <iostream>
using namespace std;
class Node {
   public:
   int val;
   Node* next;
   Node(int val) {
      this->val = val;
      next = NULL;
   }
};
void solve(Node* head, int key) {
   while(head) {
      if(head->val == key) {
         cout << "Yes";
         return;
      }
      head = head->next;
   }
   cout << "No";
}
int main() {
   Node* head = new Node(52);
   head->next = new Node(4651);
   head->next->next = new Node(42);
   head->next->next->next = new Node(5);
   head->next->next->next->next = new Node(12587);
   head->next->next->next->next->next = new Node(874);
   head->next->next->next->next->next->next = new Node(8);
   solve(head, 12587);
   return 0;
}

输出

Yes

示例

现在我们将使用递归方法来解决相同的问题 -

#include <iostream>
using namespace std;
class Node {
   public:
   int val;
   Node* next;
   Node(int val) {
      this->val = val;
      next = NULL;
   }
};
void solve(Node* head, int key) {
   if(head == NULL) {
      cout << "No";
   } else if(head->val == key) {
      cout << "Yes";
   } else {
      solve(head->next, key);
   }
}
int main() {
   Node* head = new Node(52);
   head->next = new Node(4651);
   head->next->next = new Node(42);
   head->next->next->next = new Node(5);
   head->next->next->next->next = new Node(12587);
   head->next->next->next->next->next = new Node(874);
   head->next->next->next->next->next->next = new Node(8);
   solve(head, 12587);
   return 0;
}

输出

Yes

结论

时间复杂度为 O(n)。我们使用了迭代方法来解决这个问题。尝试使用递归方法解决此问题。

Prateek Jangid

更新于: 2022年8月10日

5K+ 浏览量

开启你的 职业生涯

通过完成课程获得认证

立即开始