Convert Binary Number in a Linked List to Integer

Convert Binary Number in a Linked List to Integer - 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.

Input & Output

Example 1 — Basic Binary Conversion

$ Input: head = [1,0,1]

› Output: 5

💡 Note: Binary number 101₂ = 1×4 + 0×2 + 1×1 = 5 in decimal

Example 2 — Single Bit

$ Input: head = [0]

› Output: 0

💡 Note: Single bit 0 represents decimal 0

Example 3 — Longer Binary Number

$ Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,1,0,0,1,1,0,0,1,0]

› Output: 1234321

💡 Note: Long binary sequence converts to decimal 1234321

Constraints

The linked list is not empty
Number of nodes is in the range [1, 30]
Each node's value is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input

Linked list with binary digits: [1,0,1]

Process

Convert binary 101 to decimal using positional values

Output

Return decimal value: 5

Key Takeaway

🎯 Key Insight: Each bit contributes to the final value based on its position - multiply by 2 and add the current bit

Asked in

M Microsoft 15 a Amazon 12 A Apple 8 G Google 6

The key insight is that we can convert binary to decimal by processing each bit from left to right, doubling our current result and adding the new bit. The optimal approach uses direct conversion in a single pass. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Convert to String First	O(n)	O(n)	Traverse linked list to build binary string, then convert to decimal
Direct Conversion	O(n)	O(1)	Build decimal value directly while traversing the linked list once

Convert to String First — Algorithm Steps

Step 1: Traverse linked list and build binary string
Step 2: Convert binary string to decimal integer

Visualization

Tap to expand

Step-by-Step Walkthrough

Traverse List

Walk through linked list collecting bits

Build String

Concatenate bits into binary string

Convert

Parse binary string to get decimal result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

int solution(struct ListNode* head) {
    if (!head) return 0;
    
    // Build binary string
    char binaryStr[100] = "";
    struct ListNode* current = head;
    int index = 0;
    while (current) {
        binaryStr[index++] = '0' + current->val;
        current = current->next;
    }
    binaryStr[index] = '\0';
    
    // Convert binary string to decimal
    int result = 0;
    for (int i = 0; i < strlen(binaryStr); i++) {
        result = result * 2 + (binaryStr[i] - '0');
    }
    return result;
}

struct ListNode* buildLinkedList(int* arr, int size) {
    if (size == 0) return NULL;
    struct ListNode* head = malloc(sizeof(struct ListNode));
    head->val = arr[0];
    head->next = NULL;
    
    struct ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = malloc(sizeof(struct ListNode));
        current->next->val = arr[i];
        current->next->next = NULL;
        current = current->next;
    }
    return head;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int arr[100];
    int size = 0;
    
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        if (token[0] >= '0' && token[0] <= '9') {
            arr[size++] = atoi(token);
        }
        token = strtok(NULL, "[,]");
    }
    
    struct ListNode* head = buildLinkedList(arr, size);
    printf("%d\n", solution(head));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single traversal through n nodes to build string, plus O(n) for string conversion

✓ Linear Growth

Space Complexity

O(n)

String storage requires space proportional to number of nodes

⚡ Linearithmic Space

187.0K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Convert to String First — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler