Leetcode – Convert Binary Number in a Linked List to Integer Solution

Spread the love

The problem titled “Convert Binary Number in a Linked List to Integer” offers a classic example of how data structures like linked lists can be leveraged to solve algorithmic problems. While the problem itself is straightforward, various approaches to solving it help illuminate fundamental concepts in Python programming and computer science. This comprehensive guide aims to explain these approaches in depth.

Table of Contents

  1. Problem Description
  2. Basics of Linked Lists
  3. Naive Approach: Convert to String
  4. Optimized Approach: Bit Manipulation
  5. Further Optimization: In-Place Manipulation
  6. Testing and Validation
  7. Time and Space Complexity Analysis
  8. Conclusion

1. Problem Description

The task is to convert a binary number represented in a singly linked list to its integer representation. Each node in the linked list contains either ‘0’ or ‘1’. You are supposed to return the decimal value of this binary number.

Example:

Linked List: 1 -> 0 -> 1

Decimal Output: 5

2. Basics of Linked Lists

A linked list is a data structure consisting of nodes that hold a data value and a reference to the next node in the list. In Python, a simple linked list node can be represented as:

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

3. Naive Approach: Convert to String

Algorithm:

  1. Traverse the linked list, collecting each node’s value and appending it to a string.
  2. Convert the binary string to an integer.

Python Code:

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

def getDecimalValue(head):
    binary_number = ""
    current_node = head
    
    while current_node:
        binary_number += str(current_node.val)
        current_node = current_node.next
    
    return int(binary_number, 2)

4. Optimized Approach: Bit Manipulation

In this approach, we eliminate the need to store the binary string and instead calculate the decimal value directly as we traverse the linked list.

Algorithm:

  1. Initialize a variable num to zero.
  2. Traverse the linked list. For each node:
    • Left-shift num by 1 bit to make space for the next bit.
    • Add the node’s value to num.

Python Code:

def getDecimalValue(head):
    num = 0
    current_node = head
    
    while current_node:
        num = (num << 1) | current_node.val
        current_node = current_node.next
    
    return num

5. Further Optimization: In-Place Manipulation

Since we’re working with a simple singly linked list, the optimized approach is already efficient. Therefore, further optimization might not be necessary for this specific problem.

6. Testing and Validation

  1. Test with small linked lists with only ‘0’s or ‘1’s.
  2. Test with larger linked lists containing a random mix of ‘0’s and ‘1’s.
  3. Test with linked lists of varying lengths.

7. Time and Space Complexity Analysis

  1. Naive Approach:
    • Time Complexity: O(n)
    • Space Complexity: O(n) (for storing the binary string)
  2. Optimized Approach:
    • Time Complexity: O(n)
    • Space Complexity: O(1)

The optimized approach offers a better space complexity than the naive approach, while both approaches have the same time complexity.

8. Conclusion

The “Convert Binary Number in a Linked List to Integer” problem is a straightforward application of linked list manipulation and bit manipulation. It serves as a great exercise for understanding these basic computer science topics. We covered a naive approach that first converts the linked list to a binary string and then to its decimal value. We also looked at an optimized approach that directly computes the decimal value by traversing the list once.

Leave a Reply