Programa C++ para buscar un elemento en una lista vinculada

Escriba una función que busque una clave ‘x’ dada en una lista dada de enlaces simples. La función debe devolver verdadero si x está presente en la lista enlazada y falso en caso contrario.

bool search(Node *head, int x)

Por ejemplo, si la clave a buscar es 15 y la lista enlazada es 14->21->11->30->10, entonces la función debería devolver falso. Si la clave a buscar es 14, entonces la función debería devolver verdadero.
Solución iterativa: 

1) Initialize a node pointer, current = head.
2) Do following while current is not NULL
    a) current->key is equal to the key being searched return true.
    b) current = current->next
3) Return false 

A continuación se muestra la implementación iterativa del algoritmo anterior para buscar una clave determinada. 

// Iterative C++ program to search
// an element in linked list
#include <bits/stdc++.h>
using namespace std;
 
// Link list node
class Node
{
    public:
    int key;
    Node* next;
};
 
/* Given a reference (pointer to pointer) to
   the head of a list and an int, push a new
   node on the front of the list. */
void push(Node** head_ref, int new_key)
{
    // Allocate node
    Node* new_node = new Node();
 
    // Put in the key
    new_node->key = new_key;
 
    // Link the old list off the
    // new node
    new_node->next = (*head_ref);
 
    // Move the head to point to the
    // new node
    (*head_ref) = new_node;
}
 
// Checks whether the value x is
// present in linked list
bool search(Node* head, int x)
{
    Node* current = head;
    while (current != NULL)
    {
        if (current->key == x)
            return true;
        current = current->next;
    }
    return false;
}
 
// Driver code
int main()
{
    // Start with the empty list
    Node* head = NULL;
    int x = 21;
 
    // Use push() to construct list
    // 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;
}
// This is code is contributed by rathbhupendra

Producción: 

Yes

Complejidad de tiempo: O(n), donde n representa la longitud de la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.

Solución recursiva: 

bool search(head, x)
1) If head is NULL, return false.
2) If head's key is same as x, return true;
3) Else return search(head->next, x) 

A continuación se muestra la implementación recursiva del algoritmo anterior para buscar una clave determinada.

// Recursive C++ program to search
// an element in linked list
#include <bits/stdc++.h>
using namespace std;
 
// Link list node
struct Node
{
    int key;
    struct Node* next;
}; 
 
/* Given a reference (pointer to pointer) to
   the head of a list and an int, push a new
   node on the front of the list. */
void push(struct Node** head_ref,
          int new_key)
{
    // Allocate node
    struct Node* new_node =
           (struct Node*) malloc(sizeof(struct Node));
 
    // Put in the key
    new_node->key = new_key;
 
    // Link the old list off the new node
    new_node->next = (*head_ref);
 
    // Move the head to point to
    // the new node
    (*head_ref) = new_node;
}
 
// Checks whether the value x is
// present in linked list
bool search(struct Node* head, int x)
{
    // Base case
    if (head == NULL)
        return false;
     
    // If key is present in current
    // node, return true
    if (head->key == x)
        return true;
 
    // Recur for remaining list
    return search(head->next, x);
}
 
// Driver code
int main()
{
    // Start with the empty list
    struct Node* head = NULL;
    int x = 21;
 
    // Use push() to construct list
    // 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;
}
// This code is contributed by SHUBHAMSINGH10

Producción:  

Yes

Complejidad de tiempo: O(n), donde n representa la longitud de la lista enlazada dada.
Espacio auxiliar: O(n), debido a la pila de llamadas recursivas donde n representa la longitud de la lista enlazada dada.

Consulte el artículo completo sobre Buscar un elemento en una lista vinculada (iterativa y recursiva) para obtener más detalles.