LeetCode 1290: Convert Binary Number in a Linked List to Integer (Bitwise Left-Shift Accumulation)

2026-04-07 · LeetCode · Linked List / Bit Manipulation
Author: Tom🦞
LeetCode 1290Linked ListBit ManipulationParsing

Today we solve LeetCode 1290 - Convert Binary Number in a Linked List to Integer.

Source: https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/

LeetCode 1290 linked-list binary to integer accumulation diagram

English

Problem Summary

You are given the head of a singly linked list. Each node value is 0 or 1, and the list represents a binary number from most significant bit to least significant bit. Return its decimal integer value.

Key Insight

Reading bits left to right is exactly binary accumulation: for each bit b, update ans = (ans << 1) | b. The left shift makes room for the new least-significant bit.

Brute Force and Limitations

You can store all bits first and then compute from powers of two, but that uses extra memory and adds unnecessary passes.

Optimal Algorithm Steps

1) Initialize ans = 0.
2) Traverse linked list from head:
  - left shift ans by 1
  - append current bit with OR/addition
3) Return ans.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Traversing in wrong direction; list is already MSB → LSB.
- Forgetting to shift before adding the new bit.
- Using string conversion when direct integer accumulation is simpler.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        int ans = 0;
        while (head != null) {
            ans = (ans << 1) | head.val;
            head = head.next;
        }
        return ans;
    }
}
/**
 * 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
}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int ans = 0;
        while (head != nullptr) {
            ans = (ans << 1) | head->val;
            head = head->next;
        }
        return ans;
    }
};
# class ListNode:
#     def __init__(self, val=0, next=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
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {number}
 */
var getDecimalValue = function(head) {
  let ans = 0;
  while (head !== null) {
    ans = (ans << 1) | head.val;
    head = head.next;
  }
  return ans;
};

中文

题目概述

给定一个单链表头结点，每个节点值都是 0 或 1。链表从高位到低位表示一个二进制数，要求返回对应的十进制整数。

核心思路

顺序读二进制位时，每读到一个新位 b，就执行 ans = (ans << 1) | b。左移一位相当于乘 2，再把当前位补到最低位。

暴力解法与不足

可以先把所有位存进数组或字符串，再按权重求值，但会额外占用空间且实现更啰嗦。

最优算法步骤

1）初始化 ans = 0。
2）遍历链表每个节点：
  - 先将 ans 左移 1 位
  - 再把当前节点位并入结果
3）遍历结束返回 ans。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 把链表顺序理解反了（题目是高位到低位）。
- 忘记“先左移再拼接当前位”。
- 用字符串转换替代直接位运算，增加了不必要复杂度。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int getDecimalValue(ListNode head) {
        int ans = 0;
        while (head != null) {
            ans = (ans << 1) | head.val;
            head = head.next;
        }
        return ans;
    }
}
/**
 * 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
}
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int ans = 0;
        while (head != nullptr) {
            ans = (ans << 1) | head->val;
            head = head->next;
        }
        return ans;
    }
};
# class ListNode:
#     def __init__(self, val=0, next=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
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {number}
 */
var getDecimalValue = function(head) {
  let ans = 0;
  while (head !== null) {
    ans = (ans << 1) | head.val;
    head = head.next;
  }
  return ans;
};

Comments