要在链表中搜索元素，我们必须迭代整个链表，将每个节点与所需数据进行比较，并继续搜索直到获得匹配。因为链表不提供随机访问，所以我们必须从第一个节点开始搜索。

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

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

我们已经获取了一个列表，我们需要在该列表中查找该元素是否存在于该列表中，并使用提供的键为 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

算法（步骤）

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

• 将头部设置为空。

• 向链接列表添加一些项目

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

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

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

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

示例

例如，我们有一个链表，如“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)。我们使用迭代方法来解决这个问题。用递归方法尝试这个问题。