Problem

Submissions

Hints & solutions

Discuss

Search in a Linked List

Easy

0/40

Average time to solve is 10m

Contributed by

118 upvotes

Asked in company

ONEPERCENT SOFTWARE (OPC) PRIVATE LIMITED

Problem statement

You are given a Singly Linked List of integers with a head pointer. Every node of the Linked List has a value written on it.

A sample Linked List:

Now you have been given an integer value, 'K'. Your task is to check whether a node with a value equal to 'K' exists in the given linked list. Return 1 if node exists else return 0.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains space-separated integers denoting the values of nodes of the Linked List. 

The Linked List is terminated with -1. Hence, -1 is never a node value of the Linked List.

The second line contains a single integer 'K', which is desired to be checked in the Linked List.

Output Format:

The only line contains 1 if the desired value 'K' exists in the Linked List, otherwise, print 0.

Note:

You do not need to print anything; it has already been handled. Just implement the given function.

Sample Input 1:

3 6 2 7 9 -1
2

Sample Output 1:

Explanation for Sample Input 1:

As value 2 exists in the given linked list. So we will return 1 in this case.

Sample Input 2:

1 2 3 7 -1
7

Sample Output 2:

Explanation for Sample Input 2:

As the value 7 exists in the Linked List, our answer is 1.

Expected Time Complexity:

Try solving this in O(L).

Constraints:

1 <= 'L' <= 10^5
1 <= 'data' <= 10^9 and 'data' != -1
1 <= 'K' <= 10^9   

Where 'L' represents the total number of nodes in the Linked List, 'data' represents the value at each node, and 'K' is the given integer.

Time Limit: 1 sec.

Hint 1

Hint 2

Think of a solution to traverse the Linked List recursively and then check.

Approaches (2)

Approach 1

Approach 2

Recursive Approach

Let's try to build a recursive solution to this problem

The recursive function has three cases:

The Head is NULL(it means that we have reached the end of the linked list without finding value ‘K’ that means the particular value is not present in the Linked List. So, in this case, we will return 0 as our answer).
The Head is Not NULL, and the value of the head is equal to the desired value ‘K’ we will return 1 in this case as we found the desired value in the Linked List.
The Head is Not NULL, and the current value is not equal to the desired value ‘K’, so it will recur to the next node of the head and undergo the same process there.

Time Complexity

O(N), where ‘N’ is the number of nodes in the Linked List.

We are doing only a single traversal of the Linked List, which takes O(N) in the worst case. Hence the overall complexity will be O(N).

Space Complexity

O(N), where ‘N’ is the number of nodes in the Linked List.

In the worst case, the maximum depth of the recursion stack can take O(N) space. Hence the overall complexity will be O(N).

(100% EXP penalty)

Search in a Linked List

Console