C++程序在链表中搜索元素

编写一个函数，该函数在给定的单向链表中搜索给定的键“x”。如果x存在于链表中，则该函数应返回true，否则返回false。

bool search(Node *head, int x)

例如，如果要搜索的键是15且链表为14->21->11->30->10，则函数应返回false。如果要搜索的键是14，则该函数应返回true。

迭代解法:

1) 初始化一个节点指针current = head
2) 当current不为NULL时执行以下操作
a) 如果current的key与要搜索的key相等，则返回true。
b) current = current->next
3) 返回false

下面是以上算法的迭代实现，用于搜索给定键的节点。

// 迭代式C++程序中搜索链表元素
#include <bits/stdc++.h>
using namespace std;
 
// 链表节点
class Node
{
    public:
    int key;
    Node* next;
};
 
/* 给定列表头的引用（指向指针）和int，将新节点推到列表的前面。*/
void push(Node** head_ref, int new_key)
{
    // 分配节点
    Node* new_node = new Node();
 
    // 将键值输入新的节点
    new_node->key = new_key;
 
    // 链接新节点中旧列表的
    // next指向head_ref
    new_node->next = (*head_ref);
 
    // 将head 指向新节点
    (*head_ref) = new_node;
}
 
// 检查值 X 是否在链表中
bool search(Node* head, int x)
{
    Node* current = head;
    while (current != NULL)
    {
        if (current->key == x)
            return true;
        current = current->next;
    }
    return false;
}
 
// 驱动程序main函数
int main()
{
    // 以空列表开始
    Node* head = NULL;
    int x = 21;
 
    // 使用push()构造列表
    // 14->21->11->30->10
    push(&head;, 10);
    push(&head;, 30);
    push(&head;, 11);
    push(&head;, 21);
    push(&head;, 14);
 
    search(head, 21)? cout<<"Yes" : cout<<"No";
    return 0;
}
// 该代码由rathbhupendra贡献```

输出:

Yes

时间复杂度: O(n)，其中n表示给定链表的长度。

辅助空间: O(1)，不需要额外空间，因此为常数。

递归解法:

bool search(head, x)
1) 如果head为空，则返回false。
2) 如果head的key与x相同，则返回true；
3) 否则返回search(head->next, x)

下面是以上算法的递归实现，用于搜索给定键的节点。

// 递归查找链表中的元素的C++程序
#include <bits/stdc++.h>
using namespace std;
 
// 链表节点
struct Node
{
    int key;
    struct Node* next;
}; 

/* 给定一个指向指针的引用（指向头节点）和一个整数，将一个新节点推到链表的前面。*/
void push(struct Node** head_ref, int new_key)
{
    // 分配节点
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));

    // 添加键
    new_node->key = new_key;

    // 把新节点的旧链表连接起来
    new_node->next = (*head_ref);

    // 将头指针移动到指向新节点
    (*head_ref) = new_node;
}

// 检查链表中是否存在值x
bool search(struct Node* head, int x)
{
    // 基本情况
    if (head == NULL)
        return false;
     
    // 如果key在当前节点中，则返回true
    if (head->key == x)
        return true;

    // 递归处理剩余节点
    return search(head->next, x);
}

// 主驱动程序
int main()
{
    // 从空链表开始
    struct Node* head = NULL;
    int x = 21;

    // 用push()构建链表
    // 14->21->11->30->10
    push(&head, 10);
    push(&head, 30);
    push(&head, 11);
    push(&head, 21);
    push(&head, 14);

    search(head, 21)? cout << "Yes" : cout << "No";
    return 0;
}
// 本代码由 SHUBHAMSINGH10 提供```

输出：