Abstract / Summary

Traverse the linked list to collect binary digits and convert them to an integer.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 81% (600k+ submissions).

Typical patterns to solve this problem:

• Linked List
• Math

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a method that interprets a singly-linked list as a binary number and returns its decimal representation. Each node stores a single binary digit (0 or 1). The algorithm walks the list once, progressively building the integer value by shifting the accumulated result left (equivalent to multiplying by two) and adding the current node’s bit. The final integer is then returned.

Initialization

The method begins by creating a variable to hold the running total of the conversion.

result = 0

This variable is set to zero before any nodes are processed, establishing a clean base for the subsequent arithmetic.

Traversal Loop

The core of the conversion is a while loop that continues as long as there are nodes remaining in the list.

while head:
    result *= 2
    result += head.val
    head = head.next

Inside the loop three operations occur in sequence:

• The current result is multiplied by two, effectively shifting its binary representation left by one position.
• The value of the current node (head.val)-which is guaranteed to be either 0 or 1-is added to the shifted total.
• The pointer head advances to the next node, preparing for the next iteration.

These steps ensure that each bit from the most-significant to the least-significant contributes correctly to the final integer.

Return Statement

After the loop has exhausted all nodes, the accumulated integer is returned.

return result

At this point result holds the decimal value corresponding to the binary number encoded by the linked list.

Edge Cases Handled

The algorithm gracefully manages several boundary conditions without additional checks:

• Empty List - If head is None from the start, the while condition fails immediately, leaving result at its initial value of 0. The method returns 0, which is the correct decimal representation of an empty (or all-zero) binary sequence.
• Single-Node List - With only one node, the loop executes once. Multiplying result by two has no effect on the initial zero, and adding the node’s value yields either 0 or 1, matching the expected decimal output.
• Leading Zeros - When the list begins with one or more 0 nodes, each iteration still multiplies the current total by two and adds zero, preserving the correct positional weight. The final result reflects the true value after all bits are processed, ignoring any non-significant leading zeros.
• Maximum Length Within Integer Limits - The method relies on Python’s arbitrary-precision integers, so even very long binary sequences are handled correctly without overflow concerns.

Performance Optimizations

The implementation exhibits several efficiency choices:

• In-Place Accumulation - By updating a single integer variable (result) rather than constructing auxiliary data structures (such as strings or arrays), the algorithm minimizes memory usage and avoids the overhead of additional allocations.
• Bitwise-Equivalent Arithmetic - Multiplying by two and adding the current bit mirrors a left-shift operation. In Python, integer multiplication by a small constant is highly optimized, providing speed comparable to explicit bitwise shifts while keeping the code readable.
• Single Pass Traversal - The list is visited exactly once. No secondary passes or backtracking are required, guaranteeing linear time proportional to the number of nodes.
• No Function Calls Inside Loop - All operations inside the loop are primitive arithmetic and attribute accesses. This reduces call-stack overhead and keeps the inner loop tight, contributing to faster execution for large inputs.

Imagine you have a long train of small toy cars connected one after another. Each car has a secret number painted on it which is either a zero or a one. This code is like a little helper walking down the line of cars starting from the very front.

The helper moves along the train one car at a time. Every time the helper moves to a new car, it takes the total number collected so far and doubles it, just like stretching a piece of dough to make room for more. After stretching that number, the helper looks at the number on the current car and adds that value to the pile. Once the helper has looked at every single car in the line, it holds the final total number in its hands.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python	C++			Java						TS
	WalkCCC	Python	C++			Java
	leetcode.ca	Python	C++	JS	C#	Java	Go		C	PHP	Rust	TS
	Progiez	Python	C++			Java
github	BigEggStudy				C#
	black-shadows		C++
	chandansgowda	Python
	charles-wangkai					Java
	DimitrisJim								C
	everthis			JS
	fartem							Ruby
	fpdjsns		C++
	fsq		C++
	Garvit244	Python
	halfrost						Go
	JoshCrozier			JS
	keineahnung2345		C++
	Krazune			JS
	muhammadfarhankt						Go
	pruthvikp	Python
	qiyuangong	Python
	shreymehul				C#
	suxrobGM				C#
	trung-hn	Python
	varunu28					Java
	YuriSpiridonov	Python
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C, C++, C#, Go, Java, JavaScript, PHP, Python, Rust, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
chandansgowda	Python
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fpdjsns	C++
fsq	C++
Garvit244	Python
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	JavaScript
muhammadfarhankt	Go
pruthvikp	Python
qiyuangong	Python
shreymehul	C#
suxrobGM	C#
trung-hn	Python
varunu28	Java
YuriSpiridonov	Python

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality