Searching in Singly Linked List in C++.

Example:
Input: 10->15->9->12->20->11, key = 15
Output: True

Input: 12->32->8->10, key = 11
Output: False

• Create a temp pointer and initialize it with the head. 
• Run a while loop with condition temp not equal to NULL.
• Compare the value present in the temp node with the key value and return true if the value matches else move to the next node. (temp = temp->next)
• Return false if the key value is not found in the list. 

//C++ Example of Searching in Singly Linked List
#include<iostream>
using namespace std;

class Node{
    public:
    int data;
    Node *next;
    //constructor
    Node(int data){
        this->data = data;
        this->next = NULL;
    }
};

//Adding node at the end of the list
Node *insertEnd(Node *head, int data){
    //create a new node
    Node *new_node = new Node(data);
    Node *temp = head;
    //when list is empty
    if(temp == NULL){
        head = new_node;
    }
    else{
        while (temp->next != NULL)
        {
            temp = temp->next;
        }
        temp->next = new_node;
    }
    return head;
}
//Searching a key in linked list
bool searchList(Node *head, int key){
    //when list is empty
    if(head == NULL){
        return false;
    }
    //when list is not empty
    else{
        Node *temp = head;
        while (temp != NULL){
            if(temp->data == key)
              return true;
            temp = temp->next;  
        }
    }
    return false;
}
//Traversing Linked List
void display(Node *head){
    Node *temp = head;

    while(temp != NULL){
        cout<<temp->data<<" ";
        temp = temp->next;
    }
}

int main(){
    Node *head = NULL;
    head = insertEnd(head, 12);
    head = insertEnd(head, 13);
    head = insertEnd(head, 22);
    head = insertEnd(head, 25);
    head = insertEnd(head, 10);

    cout<<"Linked List: ";
    display(head);

    cout<<"\nKey is present in the list: ";
    if(searchList(head, 25))
       cout<<"True"<<endl;
    else
       cout<<"False"<<endl;   

    return 0;   
}

Linked List: 12 13 22 25 10
Key is present in the list: True

• Time Complexity: O(n), here is the number of nodes present in the linked list.
• Space Complexity: O(1)