---

1. Problem Summary

You are given the head of a singly linked list, where each node contains a value of either:

0 or 1

These node values represent a binary number, where:

• The head node contains the most significant bit (MSB)
• The last node contains the least significant bit (LSB)

Your task is to:

• Read the binary number represented by the linked list
• Convert it into a decimal integer
• Return the resulting integer

Example interpretation:
If the linked list is:

1 → 0 → 1

This represents binary 101, which equals decimal 5.

---

2. Key Insights

Linked list ordering matches binary digit significance

Since the list starts with the MSB, we process from head to tail.

Binary accumulation rule

As we traverse, each new bit is appended using:

result = result * 2 + node.val

This works because multiplying by 2 shifts left in binary.

No need to store digits or reverse list

We compute progressively in a single pass.

Constraints allow safe integer representation

Given list length up to about 30 bits, result fits easily in int.

---

3. Approach

Iterative traversal with binary accumulation

Steps:

1. Initialize result = 0
2. Traverse through linked list nodes
3. At each node: result = result * 2 + current.val
4. After reaching the end, return result

This produces the decimal equivalent efficiently.

---

4. Time and Space Complexity

Time Complexity: O(N)

We visit each node exactly once.

Space Complexity: O(1)

Only a single integer accumulator is used.

---

5. Java Solution

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

class Solution {
    public int getDecimalValue(ListNode head) {
        int result = 0;

        while (head != null) {
            result = result * 2 + head.val;
            head = head.next;
        }

        return result;
    }
}

---

6. Dry Run Examples

Example 1

Input Linked List:

1 → 0 → 1

Processing:

Initial result = 0

Node 1:
result = 0 * 2 + 1 = 1

Node 0:
result = 1 * 2 + 0 = 2

Node 1:
result = 2 * 2 + 1 = 5

Final Output:

5

---

Example 2

Input:

0 → 0

result = 0
result = 0

Output:

0

---

Example 3

Input:

1 → 1 → 1 → 1

Binary 1111 = decimal 15

Output:

15

---

Example 4

Input:

0 → 1 → 0 → 0 → 1

Binary = 01001
Decimal = 9

Output:

9

---

7. Why This Solution Works

• Reads bits in correct order
• Uses binary left shift logic naturally
• Avoids conversions to strings or arrays
• Uses constant space
• Works for any linked list length within constraints
• Clean and intuitive implementation

---

8. Common Mistakes

1. Reversing the list unnecessarily
2. Converting to string then parsing (less efficient)
3. Using Math.pow repeatedly (slow and error-prone)
4. Treating list as least significant bit first
5. Overflow worries (not needed for this problem)