Code Implementation

# 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:
        num = 0
        while head:
            num = num * 2 + head.val
            head = head.next
        return num
      

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int num = 0;
        while (head) {
            num = num * 2 + head->val;
            head = head->next;
        }
        return num;
    }
};
      

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

class Solution {
    public int getDecimalValue(ListNode head) {
        int num = 0;
        while (head != null) {
            num = num * 2 + head.val;
            head = head.next;
        }
        return num;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
var getDecimalValue = function(head) {
    let num = 0;
    while (head) {
        num = num * 2 + head.val;
        head = head.next;
    }
    return num;
};
      

Problem Description

Given the head of a singly-linked list, where each node contains a value of either 0 or 1, interpret the linked list as a binary number. The most significant bit comes first (at the head). Your task is to return the decimal (base-10) value of the binary number represented by the linked list.

• Each node's value is either 0 or 1.
• The input list is non-empty.
• There is exactly one valid solution for each input.
• You should not reuse or modify the nodes; just compute the value.

Thought Process

To solve this problem, we need to convert a sequence of binary digits stored in a linked list into its decimal representation. At first glance, one might consider traversing the list, collecting digits into a string or array, then converting that to an integer. But that requires extra storage.

Upon reflection, we realize that as we traverse the list from head to tail (from most significant to least significant bit), we can build the number incrementally. Each time we encounter a new digit, we shift the current value left by one bit (multiply by 2) and add the new digit. This mimics how you would compute a decimal number digit-by-digit.

This approach is both space- and time-efficient, avoiding unnecessary storage or complex operations.

Solution Approach

• Initialize a variable (e.g., num) to 0. This will store our accumulating decimal value.
• Traverse the linked list node by node, starting from the head.
• For each node:
  • Multiply num by 2 (equivalent to shifting left in binary).
  • Add the current node's value (0 or 1) to num.
• Continue until the end of the list is reached (i.e., head becomes null).
• Return the final value of num as the decimal representation.

This method leverages the properties of binary numbers and linked lists. No additional data structures are needed, and each node is visited only once.

Example Walkthrough

Let's use the input linked list: 1 -> 0 -> 1

• Start: num = 0
• First node (1): num = 0 * 2 + 1 = 1
• Second node (0): num = 1 * 2 + 0 = 2
• Third node (1): num = 2 * 2 + 1 = 5

The binary number 101 is 5 in decimal, which is the correct output.

Time and Space Complexity

• Brute-force approach: If we first collect all digits in an array or string, then convert, the time complexity is O(n) for traversal and O(n) for conversion, with O(n) extra space.
• Optimized approach (as above): We traverse the list once, doing constant-time work per node. Thus, time complexity is O(n), where n is the number of nodes. Space complexity is O(1) because we only use a fixed number of variables.

The optimized approach is both time- and space-efficient.

Summary

This problem demonstrates how to incrementally build a decimal value from a binary number represented in a linked list, using bitwise logic and simple arithmetic. The key insight is to update the result as we traverse, multiplying by 2 and adding the current digit, mimicking how binary numbers work. The solution is elegant, requiring only a single traversal and constant space.