Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Search in Linked List

EASYProblemSolveExternal Links

Description

Given the head of a singly linked list and an integer key, determine whether the key exists in the linked list.

Return true if any node in the list contains a data value equal to the key. Otherwise, return false.

You need to traverse the list and check each node's value against the given key.

Examples

Example 1

Input: head: 1 → 2 → 3 → 4, key = 3

Output: true

Explanation: Starting from head, we traverse node 1 (not 3), node 2 (not 3), then node 3 — which matches our key. We immediately return true. Node 4 is never visited because we found the answer early.

Example 2

Input: head: 10 → 20 → 30 → 40, key = 15

Output: false

Explanation: We traverse the entire list — 10, 20, 30, 40 — and none of them equals 15. After reaching null past node 40, we return false.

Example 3

Input: head: 7, key = 7

Output: true

Explanation: The list has only one node with value 7, which matches the key. We return true immediately after checking the very first node.

Constraints

  • 1 ≤ number of nodes ≤ 10^5
  • 1 ≤ node.data ≤ 10^5
  • 1 ≤ key ≤ 10^5

Editorial

Brute Force

Intuition

Unlike arrays or hash sets, a linked list provides no random access and no built-in lookup mechanism. You cannot jump to the middle or use a hash to check membership in O(1). The only way to determine if a value exists is to walk through the list, one node at a time, comparing each node's data to the target key.

Imagine you're searching for a specific book on a shelf where books have no labels — you'd pick up each one, check its title, and either declare success or move to the next. The moment you find the book, you stop.

The strategy is straightforward:

  1. Start at the head node.
  2. At each node, compare its data with the key.
  3. If they match → return true immediately (no need to visit remaining nodes).
  4. If they don't match → move to the next node.
  5. If you reach null without finding a match → the key is not in the list, return false.

The key insight is the early exit: the moment the key is found, we stop. In the best case this happens at the very first node (O(1)), and in the worst case we scan the entire list (O(n)). On average, we scan about half the nodes.

Since there is no faster way to search an unsorted linked list — you must examine nodes one by one — this linear scan is both the simplest and the optimal approach.

Step-by-Step Explanation

Let's trace through with head: 1 → 2 → 3 → 4 and key = 3:

Step 1: Set pointer curr to the head node (value 1). The key we're searching for is 3.

Step 2: Compare curr.data (1) with key (3). They are not equal. Move curr to the next node (value 2).

Step 3: Compare curr.data (2) with key (3). They are not equal. Move curr to the next node (value 3).

Step 4: Compare curr.data (3) with key (3). They ARE equal! We found the key. Return true immediately.

We never needed to visit node 4 — the early exit saved one comparison.

Searching for Key = 3 in the Linked List — Watch how the curr pointer visits each node, compares the value with the search key, and stops immediately upon finding a match.

Now let's trace the not-found case with head: 10 → 20 → 30 and key = 15:

Searching for Key = 15 (Not Found Case) — When the key does not exist, the pointer must traverse the entire list and reach null before concluding the key is absent.

Algorithm

  1. Set a pointer curr to the head of the linked list.
  2. While curr is not null:
    a. If curr.data == key, return true.
    b. Otherwise, move curr to curr.next.
  3. If the loop ends (curr is null), return false.

Code

class Solution {
public:
    bool searchKey(int n, Node* head, int key) {
        Node* curr = head;
        
        while (curr != nullptr) {
            if (curr->data == key) {
                return true;
            }
            curr = curr->next;
        }
        
        return false;
    }
};
class Solution:
    def searchKey(self, n: int, head: Node, key: int) -> bool:
        curr = head
        
        while curr is not None:
            if curr.data == key:
                return True
            curr = curr.next
        
        return False
class Solution {
    static boolean searchKey(int n, Node head, int key) {
        Node curr = head;
        
        while (curr != null) {
            if (curr.data == key) {
                return true;
            }
            curr = curr.next;
        }
        
        return false;
    }
}

Complexity Analysis

Time Complexity: O(n)

In the worst case (key not found, or key is at the last node), we visit all n nodes in the linked list. Each visit involves a constant-time comparison and a pointer advance. The best case is O(1) when the key is in the head node.

On average, if the key is equally likely to be at any position, we check about n/2 nodes, which is still O(n).

Space Complexity: O(1)

We use only one extra pointer variable curr. No additional data structures are created regardless of the list size, so the space usage is constant.