#1290

Easy

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Convert Binary Number in a Linked List to Integer

Convert a binary number represented in a linked list to its decimal value using efficient pointer manipulation.

Problem Statement

You are given a singly linked list where each node contains either a 0 or a 1. The list represents a binary number, with the head of the list corresponding to the most significant bit.

Return the decimal representation of the binary number represented by the linked list. Your solution should focus on efficiently traversing the list and calculating the result.

Examples

Example 1

Input: head = [1,0,1]

Output: 5

(101) in base 2 = (5) in base 10

Example 2

Input: head = [0]

Output: 0

Example details omitted.

Constraints

The Linked List is not empty.
Number of nodes will not exceed 30.
Each node's value is either 0 or 1.

Solution Approach

Pointer Traversal with Bit Shifting

You can traverse the linked list and build the decimal value using bit shifting. For each node, multiply the current decimal value by 2 (shift left) and add the node's value (0 or 1). This method directly reflects the binary-to-decimal conversion process.

Building an Array or String

Alternatively, store the values of the nodes in a string or array during traversal, and later convert the string/array into an integer. This method may be less efficient but is intuitive in understanding the binary-to-decimal translation.

Direct Decimal Calculation via Recursive Approach

A recursive approach can be used, where you compute the decimal value as you traverse the linked list. By calculating the result from the tail to the head, you eliminate the need for extra space like arrays or strings.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the traversal of the linked list, which is O(n), where n is the number of nodes. Space complexity is O(1) for the pointer manipulation approach, but O(n) if you use extra space like an array or string for storing the values.

What Interviewers Usually Probe

Look for the candidate's ability to understand binary-to-decimal conversion and linked-list manipulation.
Evaluate the solution's efficiency, especially with regard to space complexity when using extra data structures.
Observe whether the candidate considers both iterative and recursive solutions for this problem.

Common Pitfalls or Variants

Common pitfalls

Not efficiently updating the result while traversing the list (e.g., skipping bit shifting or not properly accounting for the most significant bit).
Misunderstanding the linked-list structure and failing to correctly traverse each node.
Using extra space like arrays or strings without considering the impact on space complexity.

Follow-up variants

Modify the problem to handle lists with mixed 0's and 1's with a different bit-order or additional manipulations.
Extend the problem to handle binary numbers represented with negative or floating point values.
Implement the solution for cases where the linked list contains more than 30 nodes or follows a different structure (e.g., doubly linked).

FAQ

How do you convert a binary number in a linked list to a decimal number?

To convert a binary number represented by a linked list to decimal, traverse the list while shifting the current decimal value left by one and adding the node's value (0 or 1).

What are the best approaches for solving the 'Convert Binary Number in a Linked List to Integer' problem?

The best approaches include pointer traversal with bit shifting, building an array or string, or using recursion for efficient calculation.

What is the time complexity of solving this problem?

The time complexity is O(n), where n is the number of nodes in the linked list.

Can you solve this problem using recursion?

Yes, you can solve the problem using a recursive approach where the decimal value is computed as the list is traversed.

What are some common mistakes when solving this problem?

Common mistakes include not correctly shifting the bits, failing to traverse the entire linked list, or using inefficient extra space like arrays or strings.

terminal

Solution

Solution 1: Traverse the Linked List

We use a variable $\textit{ans}$ to record the current decimal value, with an initial value of $0$.

1

2

3

4

5

6

7

8

9

10

11

12

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        ans = 0
        while head:
            ans = ans << 1 | head.val
            head = head.next
        return ans

Continue Practicing

#445 add two numbers ii #382 linked list random node #1295 find numbers with even number of digits