Return the sum of all values in a linked list. An empty list sums to 0.
sumList(head)
Input format: space-separated node values.
1 → 2 → 3 // → 6
10 // → 10
(empty) // → 0
Summing a linked list is another variation on the same traversal: walk from head to tail, doing something with each value. Here, instead of collecting values or counting nodes, you fold each value into a running total.
Addition doesn't care about order — add values left-to-right, right-to-left, any order, the sum comes out the same. So you don't need to see the whole list at once or hold every value in memory. Process one value at a time, in whatever order the list gives them, and just accumulate.
If the list is empty, the loop never runs, and the total — still zero — is correctly the sum of nothing. Same pattern as counting and collecting: start with the identity value, loop while there's a current node, and the edge case resolves itself.
You could gather every value into an array first and then sum it, like the previous problem. That works, but it's wasteful — you only ever need one running number. Accumulating directly during traversal keeps the extra memory constant, whether the list has ten nodes or ten million.
Each node is visited once and does a fixed amount of work, so the total work grows linearly — and there's no way to compute an exact sum without looking at every value at least once, so this is as fast as it gets.
This is the "reduce" pattern: turn a sequence into one summary value by combining items with a running accumulator. It generalizes beyond sums — a running product, a running maximum, a running count of matches — all using the same traversal skeleton.
def sum_list(head):
total = 0
node = head
while node is not None:
total += node.val
node = node.next
return total
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.