☕ DSA Java Articles

Topics › Linked List › Learn 1D LinkedList

Search in Linked List

Medium TUF ID 905 A2Z

Java source ↗ Edit this article ↗

Problem

You are given the head of a singly linked list and an integer key. Report whether some node in the list has value key. Two common variants ask for the 0-based position of the first node holding key (or -1 when there is none) and for the number of nodes holding key; both are covered below.

Constraints: 0 ≤ n ≤ 10^5 nodes, values and key fit in a 32-bit signed integer. The list is not sorted and contains no cycle.

Example 1

list = 1 -> 2 -> 3 -> 4 -> 5, key = 4
answer = true                  // the fourth node holds 4 (index 3)

Example 2

list = 1 -> 2 -> 3 -> 4 -> 5, key = 6
answer = false                 // no node holds 6

Example 3

list = 2 -> 9 -> 2 -> 2 -> 5, key = 2
answer = true                  // first index 0, occurrences 3

The node type is the standard one with an int val and a ListNode next reference.

static class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

Approach 1: Linear scan with early exit

Intuition. There is no shortcut into a linked list. Values are not sorted, and even if they were, there is no way to jump to the middle node in constant time, so binary search does not apply. The only option is to look at nodes one after another. The one improvement over “visit everything” is to stop the moment we see the key: in the best case that is the first node, and on average it halves the work when the key is present.

Algorithm.

  1. Set temp = head.
  2. While temp != null: if temp.val == key, return true; otherwise move temp to temp.next.
  3. If the loop finishes, the key is absent; return false.
static boolean searchIterative(ListNode head, int key) {
    ListNode temp = head;
    while (temp != null) {
        if (temp.val == key) return true;
        temp = temp.next;
    }
    return false;
}

Complexity. Time O(n) in the worst case (key absent or at the tail), each node checked once. Space O(1).

Dry run on 1 -> 2 -> 3 -> 4 -> 5 with key = 4:

iteration temp.val equals key? action
1 1 no advance
2 2 no advance
3 3 no advance
4 4 yes return true

The fifth node is never examined. With key = 6 the loop visits all five nodes, temp becomes null, and false is returned. On an empty list the loop body never runs and the answer is false immediately.

Approach 2: Recursion

Intuition. The key is in the list exactly when it is at the head, or it is somewhere in the rest of the list. That sentence is already the recursive definition: an empty list contains nothing; otherwise check the head and recurse on the tail. It is worth knowing because the same shape appears in recursive deletion of all occurrences, recursive reversal, and tree search, where the recursion is genuinely needed.

Algorithm.

  1. If head == null, return false.
  2. If head.val == key, return true.
  3. Otherwise return searchRecursive(head.next, key).
static boolean searchRecursive(ListNode head, int key) {
    if (head == null) return false;
    if (head.val == key) return true;
    return searchRecursive(head.next, key);
}

Complexity. Time O(n). Space O(n) for the call stack in the worst case, one frame per node visited.

The recursive call is in tail position, but Java does not perform tail-call elimination, so each frame stays on the stack until the answer comes back. On a list of 10^5 nodes that is a real risk of StackOverflowError; the loop in Approach 1 is what you should write when the input can be long. The test file keeps the recursive depth at 5000, which the default stack handles comfortably.

Variant: position of the first match

Intuition. Reporting where the key is requires only a counter that advances in step with the node reference. The for header below updates both on each iteration, which keeps the index and the node permanently in sync.

Algorithm.

  1. Set i = 0 and t = head.
  2. For each node: if t.val == key, return i; otherwise advance t and increment i.
  3. Return -1 if the loop finishes.
static int indexOf(ListNode head, int key) {
    int i = 0;
    for (ListNode t = head; t != null; t = t.next, i++) {
        if (t.val == key) return i;
    }
    return -1;
}

Complexity. Time O(n), space O(1).

Because indexOf returns the index of the first match, searchIterative(head, key) is equivalent to indexOf(head, key) >= 0, and the tests check the two against each other on every input. With duplicates such as 2 -> 9 -> 2 -> 2 -> 5 and key = 2, the answer is 0, not 2 or 3.

Variant: counting every occurrence

Intuition. When the question is “how many nodes hold the key”, early exit is no longer allowed: a match does not tell us anything about the nodes after it. So this is a full traversal with a counter that increments on every match.

Algorithm.

  1. Set count = 0.
  2. For every node, if t.val == key, increment count.
  3. Return count.
static int countOccurrences(ListNode head, int key) {
    int count = 0;
    for (ListNode t = head; t != null; t = t.next) {
        if (t.val == key) count++;
    }
    return count;
}

Complexity. Time Θ(n), always the full list. Space O(1).

The two variants agree with the boolean search in a simple way: the key is present exactly when countOccurrences > 0 and exactly when indexOf >= 0. The test harness asserts all four methods against the same expected (index, count) pair for each input, so a bug in any one of them shows up as a disagreement.

On a sorted array, binary search finds a key in O(log n) because arr[mid] is a constant-time read. A linked list cannot provide mid without walking n / 2 nodes, which already costs O(n). Sorting the list does not help either for the same reason. If a program needs many lookups by value, the right move is a different structure: a hash set gives O(1) average membership, a balanced tree gives O(log n). A linked list is for sequences where you mostly work at the ends or at a node you already hold; its search is linear by nature, not because of a missing trick.

Edge cases and pitfalls