Search in a Singly Linked List

Given the head of a singly linked list and a target value, return true if any node holds the target, and false otherwise.

Example 1

Text

Input:  4 -> 10 -> 40 -> 5, target = 40
Output: true

Example 2

Text

Input:  4 -> 10 -> 40 -> 5, target = 7
Output: false

Searching only reads the list. The method does not change any node, so the caller can keep using the list afterwards.

A list node here is an object with a mutable next field, and null marks the end of the list. An empty list is null, so no wrapper type is needed.

Brute force: recursion

A list either is empty (the target isn't there) or has a first node. With a first node, the target is present if that node holds it or if the rest of the list contains it.

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static boolean search(ListNode head, int target) {
        if (head == null) return false;
        return head.val == target || search(head.next, target);
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        ListNode list = fromArray(4, 10, 40, 5);
        System.out.println(search(list, 40) + " " + search(list, 7) + " " + search(null, 1));
    }
}

Output

true false false

Time: O(n). Space: O(n) for the call stack. || short-circuits, so the recursion stops as soon as the target is found. A very long list throws StackOverflowError.

Optimal: iterate with a reference

Walk a reference cur from node to node. Assigning cur = cur.next copies only the reference, not the node, so the list is untouched.

Walkthrough with target 40:

cur	val	match?
node 1	4	no
node 2	10	no
node 3	40	yes, return true

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static boolean search(ListNode head, int target) {
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == target) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        ListNode list = fromArray(4, 10, 40, 5);
        System.out.println(search(list, 40) + " " + search(list, 7) + " " + search(null, 1));
    }
}

Output

true false false

Time: O(n). Space: O(1).

The same search as a stream

Stream.iterate(seed, hasNext, next) produces seed, then next(seed), and so on, while hasNext returns true. With Objects::nonNull as hasNext and n -> n.next as next, the stream visits every node and stops at the null that ends the list. That turns a linked list into a stream, and every stream method becomes available.

Java

import java.util.Objects;
import java.util.stream.Stream;

public class Main {
    static class ListNode {
        int val;
        ListNode next;

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

    static Stream<ListNode> nodes(ListNode head) {
        return Stream.iterate(head, Objects::nonNull, n -> n.next);
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        ListNode list = fromArray(4, 10, 40, 5);
        System.out.println(nodes(list).anyMatch(n -> n.val == 40));
        System.out.println(nodes(list).map(n -> n.val).toList().indexOf(40)); // index of the match
        System.out.println(nodes(list).count());
    }
}

Output

true
2
4

Each call to nodes(list) creates a fresh stream that starts at the head. A stream can be consumed once, but the list is only read, so a new stream can be created as many times as needed. indexOf returns -1 when the value is absent. Streams add some overhead compared to the plain loop, and the complexity stays O(n) time.

Edge cases

Empty list: false.
Target in the head or the tail: the loop checks every node, including the first and last.
Duplicates: the search stops at the first match.