Problem

Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.

Return the decimal value of the number in the linked list.

The most significant bit is at the head of the linked list.

Examples

Example 1

1
2
3

Input: head = [1,0,1]
Output: 5
Explanation: (101) in base 2 = (5) in base 10

Example 2

1
2

Input: head = [0]
Output: 0

Constraints

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

Solution

Method 1 – Bitwise Linked List Traversal

Intuition

The linked list represents a binary number, with the most significant bit at the head. We can traverse the list, shifting the result left and adding the current node’s value at each step, effectively building the integer value bit by bit.

Approach

  1. Initialize ans = 0.
  2. Traverse the linked list from head to end:
    • For each node, shift ans left by 1 (multiply by 2), then add node.val.
  3. Return ans after the traversal.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int ans = 0;
        while (head) {
            ans = (ans << 1) | head->val;
            head = head->next;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

type ListNode struct {
    Val int
    Next *ListNode
}
func GetDecimalValue(head *ListNode) int {
    ans := 0
    for head != nil {
        ans = (ans << 1) | head.Val
        head = head.Next
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
class Solution {
    public int getDecimalValue(ListNode head) {
        int ans = 0;
        while (head != null) {
            ans = (ans << 1) | head.val;
            head = head.next;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

data class ListNode(var `val`: Int, var next: ListNode? = null)
class Solution {
    fun getDecimalValue(head: ListNode?): Int {
        var ans = 0
        var node = head
        while (node != null) {
            ans = (ans shl 1) or node.`val`
            node = node.next
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class ListNode:
    def __init__(self, val: int = 0, next: 'ListNode' = 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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}
impl Solution {
    pub fn get_decimal_value(head: Option<Box<ListNode>>) -> i32 {
        let mut ans = 0;
        let mut node = head;
        while let Some(n) = node {
            ans = (ans << 1) | n.val;
            node = n.next;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val ?? 0;
        this.next = next ?? null;
    }
}
class Solution {
    getDecimalValue(head: ListNode | null): number {
        let ans = 0;
        let node = head;
        while (node) {
            ans = (ans << 1) | node.val;
            node = node.next;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the number of nodes in the linked list. Each node is visited once.
  • 🧺 Space complexity: O(1), only a few variables are used.