Find first occurrence
Walk with an index counter and return the position of the first matching value. About 8 minutes.
Tracking your position
Nodes in a linked list do not know their own position. If you need to know which place a node occupies, you have to count for yourself, like counting the carriages on a train as you walk through it.
Start a counter at 0, and add 1 every time you step to the next node.
The pointer starts at the head (5), and the counter is 0. 5 is not 3. Advance.
Returning early
When searching for the first occurrence of a value, check whether the current node holds the target. If it does, return the counter immediately and stop walking, because the problem asks for the first occurrence.
Only if the loop finishes without finding a match do you answer minus one.
idx = 0
curr = head
while curr:
if curr.val == target:
return idx
idx += 1
curr = curr.next
return -1If target is the second node in a 5-node list, how many nodes does the loop examine?
- A2 nodes
- B5 nodes
- C1 node
Show the answer
2 nodes. It checks node 0, does not match, steps to node 1, matches, and returns immediately.
Find first occurrence
Given the head of a linked list and an integer target, return the 0-based index of the first node whose value equals target. If target does not appear anywhere in the list, return -1.
head = [5, 8, 3, 9], target = 3 → 2
0 ≤ number of nodes ≤ 10,000 · -1,000,000 ≤ node.val, target ≤ 1,000,000