Convert Binary Number in a Linked List to Integer - Solution & Explanation

Problem Overview: A singly linked list stores a binary number where each node contains either 0 or 1. The head represents the most significant bit. Traverse the list and convert this binary sequence into its decimal integer value.

Approach 1: Bit Manipulation (O(n) time, O(1) space)

This approach treats the traversal like constructing a binary number bit by bit. Start with result = 0. For every node, shift the current value left by one (result << 1) and add the node’s bit using | node.val or simple addition. Each iteration effectively multiplies the current value by two and appends the new bit. The algorithm performs a single pass through the linked list, making it the most direct and efficient solution. Time complexity is O(n) and space complexity is O(1).

Approach 2: Reverse Iteration and Power of Two (O(n) time, O(n) space)

This method first collects all node values into an array while iterating through the list. After that, iterate the array from right to left and compute the decimal value using powers of two. For each bit at index i, add bit * 2^position to the result. The logic mirrors standard binary-to-decimal conversion using math. While still linear time, this approach uses extra memory to store the bits before computing the final value. Time complexity is O(n) and space complexity is O(n).

Recommended for interviews: The Bit Manipulation approach is the expected solution. It processes the list in one pass with constant space and clearly demonstrates understanding of binary operations. The power-of-two approach works but adds unnecessary memory overhead. Interviewers typically want to see how you apply bit manipulation while traversing a linked list.