Occurrence of an Integer in a Linked List

Slug: occurence-of-an-integer-in-a-linked-list Difficulty: Easy Id: 700019 Topic Tags: Linked List, Data Structures Company Tags: None

Summary

Given a linked list and an integer, this problem requires you to find the frequency of that integer in the linked list. The key concept involved is traversing the linked list.

Detailed Explanation

To solve this problem, we will traverse the linked list once and keep track of the count of the given integer.

Here's a step-by-step breakdown:

Start at the head of the linked list.
Iterate through the linked list until you reach the end (i.e., NULL or None).
For each node, check if the value is equal to the target integer.
If it is, increment a counter variable.
Return the count.

Here's an ASCII art diagram of the linked list:

 1 -> 2 -> 3 -> 4 -> 5
  ^
 head

Time complexity: O(n), where n is the number of nodes in the linked list. Space complexity: O(1), as we are not using any extra space that scales with the input size.

Optimized Solutions

Java

public class Solution { public int findFrequency(Node head, int target) { int count = 0; Node current = head; while (current != null) { if (current.data == target) { count++; } current = current.next; } return count; } }