DSA SheetEasy
EditorialPractice

LINKED LIST › LINKED LIST (PART 1)

Convert Binary Number in a Linked List to Integer

EasyEditorial · 5 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

Intuitionthe binary definition already gives the update rule

A binary number grows one digit at a time from left to right. If the value formed so far is ans, appending a new binary digit moves every existing digit one place to the left, which doubles ans, and then places the new digit in the empty rightmost position. The new value is therefore 2 x ans + bit.

A left shift performs that doubling directly: ans << 1. Since each node stores either 0 or 1, bitwise OR then inserts the current digit without changing the earlier digits. Starting from zero and applying this update while following next visits the most significant bit first, exactly matching the list's order.

DIAGRAM — NOT DRAWN YET

Three linked-list nodes labeled 1, 0, and 1 appear from left to right, with arrows pointing to the next node. The first node is processed before the second, and the second before the third. Beside the current prefix, an operation shifts the prefix left by one position and places the current bit in the newly opened rightmost position. The picture makes clear that each node extends the number rather than contributing an independent decimal digit.

Approach

  1. Set ans to 0 before reading the list, because no digits have been incorporated yet and every later update should extend the same accumulated prefix.
  2. While head is not null, process exactly one binary digit and then move head to head->next, because stopping after one node would ignore the remaining digits and failing to advance would loop forever.
  3. Shift ans left by one position, because appending any binary digit doubles the value represented by the prefix already processed.
  4. Combine the shifted value with head->val using bitwise OR, because the node value is the new least significant bit and is guaranteed to be either 0 or 1.
  5. Return ans after the traversal ends, because all nodes have then been consumed in most-significant-bit-first order and the accumulator is the requested decimal value.

Complexityone pass and constant working memory

MEASUREBOUNDWHY
TimeO(n)The loop reads each node once and advances to the next node once. A singly-linked list provides no way to skip ahead, but no node is revisited, so the total work grows linearly with n.
SpaceO(1) extraOnly ans and the traversal pointer are used; the returned value is a scalar rather than stored output. The bound stays constant whether the list is short, long, balanced in no meaningful sense, or shaped as the longest allowed chain.
Here n is the number of nodes in the linked list.

Annotated solutionC++ · iterative · constant extra space

CPPRead each node once, shift the prefix, and append the current bit.
#include <vector>
using namespace std;

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 != nullptr) {
            ans = (ans << 1) | head->val;
            head = head->next;
        }

        return ans;
    }
};

The order inside the loop is the entire algorithm's key. The shift must happen before the OR: ans represents the digits already read, so the shift creates room for the new digit. Moving head afterward ensures the next iteration extends the result rather than processing the same node again.

Common mistakestwo lines that change the meaning of the traversal