AlgoViz
HomeLinked List

Search in Linked List

Medium

Linear scan, node by node

Problem

You are given the head of a singly linked list and an integer key. Return true if the key exists in the linked list, otherwise return false.

In simple words

Step through node by node, checking each value until you find the key or reach the end.

The idea

Walk from the head comparing each value with the key and return true on the first match. Without random access there is no way to binary search, so O(n) is the floor.

The trick

  • Return as soon as you match; there is nothing to gain by continuing.
  • An empty list returns false, handled by the loop condition alone.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
4
0
1
2
3

Step 1 of 2. Here's the example — head = [1, 2, 3, 4], key = 3 Values: 1, 2, 3, 4.

1/2
Optimal
timeO(n)spaceO(1)
1cur = head2while cur != null:3  if cur.val == target: return true4  cur = cur.next5return false

Input

array
[1, 2, 3, 4]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
list = 1 -> 2 -> 3, key = 2
Output:
true
Explanation:
2 is the middle node.

Example 2

Input:
list = 1 -> 2 -> 3, key = 9
Output:
false
Explanation:
9 isn't here → false.

Example 3

Input:
list = 5, key = 5
Output:
true
Explanation:
Head matches.

Constraints

  • The number of nodes in the linked list is in the range 1 <= n <= 10⁵.
  • The value of each node is in the range 1 <= Node.val <= 10⁵.
  • 1 <= key <= 10⁵

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.