How to Convert Binary Number in a Linked List to Integer?

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.

Example 1:

binary-linked-list

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

Example 2:
Input: head = [0]
Output: 0

Example 3:
Input: head = [1]
Output: 1

Example 4:
Input: head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
Output: 18880

Example 5:
Input: head = [0,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.

Hints:
Traverse the linked list and store all values in a string or array. convert the values obtained to decimal value.
You can solve the problem in O(1) memory using bits operation. use shift left operation ( << ) and or operation ( | ) to get the decimal value in one operation.

The MSB (Most Significant Bit) or the Binary Number is the Head of the linked-node, thus by following the linked nodes in the list, we can use the OR bitwise to shift the current value one position to the left and use the bitwise OR to take the current node.

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int r = 0;
        while (head) {
            r = (r << 1) | head->val;
            head = head->next;
        }
        return r;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int r = 0;
        while (head) {
            r = (r << 1) | head->val;
            head = head->next;
        }
        return r;
    }
};

We can also, use the math formula: (101, base two) = 1*2^2+0*2^1+1*2^0.

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int r = 0;
        while (head) {
            r = r * 2 + head->val;
            head = head->next;
        }
        return r;
    }
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int r = 0;
        while (head) {
            r = r * 2 + head->val;
            head = head->next;
        }
        return r;
    }
};

Both implementation require O(1) constant space, and the time complexity is O(N) where N is the number of the nodes in the linked-list.

–EOF (The Ultimate Computing & Technology Blog) —