Search for a Value in a Linked List
Solve this Problem
Given the
head of a singly linked list and an integer target, return true if target appears anywhere in the list, and false otherwise.
Unlike an array, a linked list gives no random access — the only way to reach any node is by walking next pointers from head, so a linear scan is unavoidable, sorted or not. Both an iterativeIterativeSolved with an explicit loop, keeping state (like a curr pointer) in local variables instead of the call stack. Runs in O(1) extra space here. pass with a curr pointer and a recursiveRecursiveSolved by having the function call itself on a smaller version of the same problem — here, "search the rest of the list" is the same problem as the original, just one node shorter. version that checks head and calls itself on head.next do exactly this walk; the recursive version just spends O(n) call-stack space doing it.
Test Case 1:
Input:head = [4, 9, 2, 7], target = 2
Output:true
Explanation:2 is the third node's value.
Test Case 2:
Input:head = [4, 9, 2, 7], target = 5
Output:false
Explanation:5 never appears in the list.
Test Case 3:
Input:head = [], target = 1
Output:false
Explanation:An empty list contains nothing to find.
Constraints
- ◆
0 ≤ number of nodes in head ≤ 10⁴ - ◆
-10⁹ ≤ node value, target ≤ 10⁹ - ◆
Searching an empty list must return false, not an error
🚀
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
🧪Try your own test case
| 1 | class Solution { |
| 2 | public boolean searchInLinkedList(Node head, int target) { |
| 3 | Node curr = head; |
| 4 | while (curr != null) { |
| 5 | if (curr.val == target) { |
| 6 | return true; |
| 7 | } |
| 8 | curr = curr.next; |
| 9 | } |
| 10 | return false; |
| 11 | } |
| 12 | } |
| 13 |
4
curr
9
2
7
Variables
curr
4INITIALIZE
curr starts at head, ready to check every node in order.
Step 1 / 7
Approach & Solutions
Recursive — Check Head, Recurse on the Rest
GoodIf head is null, the list (or what's left of it) is empty — target isn't here. If head.val matches, target is found. Otherwise, the answer is whatever searching the rest of the list (head.next) finds. Correct and elegant, but each recursive call adds a stack frame, so a long list uses O(n) call-stack space.
Time
O(n)Space
O(n)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public boolean searchInLinkedList(Node head, int target) {
9 if (head == null) {
10 return false;
11 }
12 if (head.val == target) {
13 return true;
14 }
15 return searchInLinkedList(head.next, target);
16 }
17}Iterative — Single Pass
OptimalWalk curr from head, comparing each node's val to target. Return true the moment a match is found; if curr runs off the end without one, target isn't in the list. Same work as the recursive version, but with no call-stack overhead.
Time
O(n)Space
O(1)Java
1// Node definition used in this problem:
2// class Node {
3// int val;
4// Node next;
5// }
6
7class Solution {
8 public boolean searchInLinkedList(Node head, int target) {
9 Node curr = head;
10 while (curr != null) {
11 if (curr.val == target) {
12 return true;
13 }
14 curr = curr.next;
15 }
16 return false;
17 }
18}