5 Best Ways to Convert a Linked List Representing a Binary Number to a Decimal Integer in Python

Rate this post

πŸ’‘ Problem Formulation: You have a singly linked list where each node contains a single digit. Those digits form a binary number when read from left to right. Your task is to convert this binary-linked list to its equivalent decimal integer. For example, given the linked list 1 -> 0 -> 1, your function should return the decimal integer 5.

Method 1: Iterative Approach

This method involves iterating over each node in the linked list, starting from the head. For each node, we iterate, the current decimal value is doubled and then increased by the node’s value. This method leverages the fact that each bit’s value is double the previous bit in a binary number.

Here’s an example:

class ListNode:
    def __init__(self, value=0, next=None):
        self.val = value
        self.next = next

def binary_list_to_decimal(head):
    num = 0
    while head:
        num = num * 2 + head.val
        head = head.next
    return num

# Create a linked list 1 -> 0 -> 1
node1 = ListNode(1)
node2 = ListNode(0)
node3 = ListNode(1)
node1.next = node2
node2.next = node3

print(binary_list_to_decimal(node1)) # Output: 5

The output of this code snippet is: 5.

This code snippet defines a simple ListNode class to represent the nodes of the linked list. The function binary_list_to_decimal takes the head of the linked list as its argument and computes the decimal equivalent by traversing the linked list only once. It is efficient and straightforward.

Method 2: Recursive Approach

The recursive approach offers a concise solution by breaking down the problem and calling the function itself with part of the problem until a base case is met. It’s a classic divide-and-conquer strategy applied to our list conversion task.

Here’s an example:

def binary_list_to_decimal_recursive(node, acc=0):
    if not node:
        return acc
    return binary_list_to_decimal_recursive(node.next, acc*2 + node.val)

# Assuming ListNode is defined as in Method 1

# Create a linked list 1 -> 0 -> 1
node1 = ListNode(1)
node2 = ListNode(0)
node3 = ListNode(1)
node1.next = node2
node2.next = node3

print(binary_list_to_decimal_recursive(node1)) # Output: 5

The output of this code snippet is: 5.

This snippet uses recursion to traverse the linked list. The function binary_list_to_decimal_recursive calls itself with the next node and the accumulated value until it reaches the end of the list. It is elegant and minimizes iterative code, but it may lead to a stack overflow if the list is too long.

Method 3: Using Bit Manipulation

Bit manipulation is an effective way to handle binary numbers. This method uses bitwise operators to move bits and compute the decimal value directly. It’s optimal for binary-related operations and exhibits low-level computing intuition.

Here’s an example:

def binary_list_to_decimal_bitwise(head):
    num = 0
    while head:
        num = (num < 0 -> 1
node1 = ListNode(1)
node2 = ListNode(0)
node3 = ListNode(1)
node1.next = node2
node2.next = node3

print(binary_list_to_decimal_bitwise(node1)) # Output: 5

The output of this code snippet is: 5.

The binary_list_to_decimal_bitwise function applies bit shifting and a bitwise OR to calculate the decimal value. It showcases an in-place manipulation of binary digits, which enhances performance and provides a clean approach to binary operations.

Method 4: Convert to String and then Decimal

This method first creates a string representation of the binary number by concatenating the values and then uses Python’s inbuilt functionality to convert the binary string to a decimal number.

Here’s an example:

def binary_list_to_string(head):
    binary_str = ""
    while head:
        binary_str += str(head.val)
        head = head.next
    return int(binary_str, 2)

# Assuming ListNode is defined as in Method 1

# Create a linked list 1 -> 0 -> 1
node1 = ListNode(1)
node2 = ListNode(0)
node3 = ListNode(1)
node1.next = node2
node2.next = node3

print(binary_list_to_string(node1)) # Output: 5

The output of this code snippet is: 5.

This function binary_list_to_string traverses the linked list to create a string representation of the binary number and then straightforwardly converts it to decimal. While this is very readable, it is not the most efficient due to string concatenation and the overhead of type conversion.

Bonus One-Liner Method 5: Using functools and operator

Python’s functools and operator modules can be combined to create a concise one-liner that reduces the linked list to a decimal number via functional programming techniques.

Here’s an example:

from functools import reduce
import operator

# Assuming ListNode is defined as in Method 1

# Create a linked list 1 -> 0 -> 1
node1 = ListNode(1)
node2 = ListNode(0)
node3 = ListNode(1)
node1.next = node2
node2.next = node3

# One-liner to convert linked list to decimal
print(reduce(lambda acc, val: acc*2 + val, (node.val for node in iter(lambda: node1 if node1 else None, node1.next)), 0))

The output of this code snippet is: 5.

The one-liner leverages reduce from functools and a generator expression to iterate through the linked list, multiplying the accumulator by 2 and adding the current value. This method is terse and functional, but readability may be compromised for those unfamiliar with functional programming concepts.

Summary/Discussion

  • Method 1: Iterative Approach. Efficient. Easy to understand. Risks being verbose for those preferring functional styles.
  • Method 2: Recursive Approach. Elegant. Minimizes loop constructs. May cause stack overflow with long lists.
  • Method 3: Bit Manipulation. Optimal for binary operations. Demonstrates low-level understanding. May be less intuitive for some.
  • Method 4: Convert to String and then Decimal. Readable. Utilizes Python’s inbuilt functions. Incurs string concatenation overhead.
  • Bonus Method 5: Using functools and operator. Concise. Demonstrates functional programming. Readability may suffer.