Given a singly linked list, write a function which will search for a value in the list. Signature of the function will be as shown below:

bool search(Node*head, int x);

head points to the first Node in the list. The function should return true is x is present in the list as false.

In a linked list only linear search can be made (No-Binary search even if the list is sorted). Hence the solution is simple,

Check each Node of the list, if value in Node == x return TRUE When the list is over return FALSE

**Non-Recursive Solution:**

bool search(Node* head, int x) { for(; head != NULL; head = head->link) { if(head->data == x) return true; } return false; }

**Recursive Solution:**

Before getting fascinated with recursion, you should know that recursion comes with its side effects

bool search(Node* head, int x) { if(head == NULL) return false; if(head->data == x) return true; search(head->link, x); }

**Time Complexity:** O(n) for both recursive & Non-Recursive implementation

**Extra Space Used:** For Non-Recursive O(1). For Recursive Solution, O(n) (Space used in the stack to store activation records of function getting called recursively.