Algorithm

Linked List Traversal

Linked List Pattern

Linked List Traversal

Given the head of a singly linked list, visit every node in order from head to tail and perform an operation on each (for example, read its value into a list, count the nodes, or search for a target). Traversal is the linked list's version of a for-loop. If the list is empty the head is null and there is nothing to visit. No new list is created — you only walk the existing one.

CONSTRAINTS
  • The number of nodes in the list is in the range [0, 10⁴]
  • -10⁵ <= Node.val <= 10⁵
EXAMPLE 1
Input: head = [1,2,3,4,5]
Output: 1, 2, 3, 4, 5
Starting from the head, each node is reached by following the previous node's link, so the values come out in the order they are chained: 1, then 2, and so on to 5.
EXAMPLE 2
Input: head = [10, 20, 30], target = 20
Output: true
Walking from the head we reach 10, then 20, which equals the target — so the value is present in the list. The answer is true regardless of what follows.
EXAMPLE 3
Input: head = []
Output: (nothing visited)
An empty list has no first node — the head is null — so there is nothing to visit and no value to report.
Is this a singly or doubly linked list?
Assume singly linked unless told otherwise: each node knows only its successor, so you can move forward but never backward. A doubly linked list adds a prev pointer, which makes backward walks and certain deletions easier at the cost of extra memory per node.
Can the list be empty, and is the head guaranteed to be non-null?
The constraints allow 0 nodes, so the head can be null. Any correct traversal must handle that by testing the pointer before dereferencing it — the standard loop does this automatically.
Am I returning the node values or the node objects themselves?
Depends on the caller — clarify it. Returning values (a plain list) is common for reporting; returning node references matters when the caller needs to keep manipulating the structure. The traversal itself is identical either way.
May I modify the nodes while traversing?
For a read-only visit, don't — leave the structure intact. If a task does require rewiring links, you must cache curr.next before overwriting it, or you lose the rest of the list.
Pointer Chasing

Traversing a linked list is like following a chain of breadcrumbs across memory. Unlike an array where you can jump to any position instantly, a linked list requires you to physically visit every preceding node to reach your destination.

The only way to navigate is to start at the Head and repeatedly follow the next pointer. Each step reveals the location of the next node. If you lose your current pointer, you lose access to the entire rest of the chain.

python
curr = head
while curr:
    # Perform operation (e.g., print or search)
    print(curr.val)
    
    # Follow the link to the next node
    curr = curr.next
Efficiency: O(N) Time

Because nodes are scattered in memory, we must visit all N nodes sequentially. There is no shortcut, making O(N) the fundamental speed limit for linked list operations.

Worked Example:[10, 20, 30]
10
curr
→
20
→
30
→
NULL
We initialize our tracker pointer 'curr' at the head of the list, which holds the value 10.
10
→
20
curr
→
30
→
NULL
We process the current node's value (10) and then shift 'curr' forward to the next node by following its pointer to 20.
10
→
20
→
30
curr
→
NULL
We process the node containing 20, then shift 'curr' forward again to point to the last node containing 30.
10
→
20
→
30
→
NULL
We process 30. Following the next pointer of the tail node leads to null, so the traversal loop terminates.
Interactive Strategy Visualization

Sequential Traversal

Strategy: Following the Chain
curr
10
25
42
67
null
Current Actionpointer = head
Search Status
Starting...
Phase 1: Initialize Head
We begin at the Head of the list. We store the memory address of this first node in our `curr` pointer variable.
O(N) Time · O(1) Space Single-Pass Traversal