Know this before you start: “Traverse with a current pointer”
Walking a linked list
Each node holds a value and a link to the next. Start at the head and follow .next until None: that's how every list problem moves.
The idea
A linked list isn't stored side by side like an array. Each node knows only its value and the next node. There's no list[i]: to reach the 5th node you follow 4 links.
The basic move is a CURRENT pointer: start at head, do something with current.val, then current = current.next, until current is None.
A dummy node placed before the head makes inserting or deleting at the front work like everywhere else.
See it step by step
Sum and length of 3 → 1 → 4
- current = 3: total 3, length 1 → current = 1
- current = 1: total 4, length 2 → current = 4
- current = 4: total 8, length 3 → current = None: stop.
In code (Python)
class ListNode:
def __init__(self, val, next=None):
self.val, self.next = val, next
def build(values):
dummy = ListNode(0)
tail = dummy
for v in values:
tail.next = ListNode(v)
tail = tail.next
return dummy.next
def to_list(head):
out, current = [], head
while current:
out.append(current.val)
current = current.next
return out
def remove_value(head, target):
dummy = ListNode(0, head) # handles removing the head too
current = dummy
while current.next:
if current.next.val == target:
current.next = current.next.next
else:
current = current.next
return dummy.next
print(to_list(build([3, 1, 4]))) # [3, 1, 4]
print(to_list(remove_value(build([1, 2, 1, 3]), 1))) # [2, 3]Reaching position i: O(i). A full walk: O(n). Inserting after a known node: O(1).
When you'll use it
- Every linked list problem: length, search, delete, merge, insert.
Common mistakes
- Losing the head because you moved it instead of a copy.
- Reading current.next.val without checking current.next exists.
