Solution For Convert Binary Number In A Linked List To Integer

Problem Statement:

Given a singly linked list with 0s and 1s, you have to convert this binary number represented by this linked list to decimal representation.

Example:

Input: head = [1,0,1] Output: 5
Explanation: (101) in decimal is 5.

Solution:

We can traverse the given linked list node by node and convert it to decimal number representation in the following way:

1. Initialize a variable result to 0.
2. Traverse the linked list till the end and for each node:
   a. Multiply the current value of result with 2 (since we are dealing with binary numbers).
   b. Add the value of the current node to result.
3. Return the final result value.

Algorithm:

1. Initialize a variable result to 0.
2. Traverse the linked list till the end:
   a. Multiply the current value of result with 2 (since we are dealing with binary numbers).
   b. Add the value of the current node to result.
3. Return the final result value.

Implementation:

int getDecimalValue(ListNode* head) {
int result = 0;
while (head != NULL) {
result = result * 2 + head->val;
head = head->next;
}
return result;
}

Time Complexity: O(n) where n is the number of nodes in the linked list.

Space Complexity: O(1) as we are not using any extra space.

Explanation:

In the above solution, we have initialized a variable result to 0 and traversed the linked list. While traversing the linked list, we have multiplied the current value of result with 2 (since we are dealing with binary numbers) and added the value of the current node to result. Finally, we have returned the final result value.

Step by Step Implementation For Convert Binary Number In A Linked List To Integer

/**
 * 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) {
        // edge case: if head is null, return 0
        if (head == null) {
            return 0;
        }
        
        // create a variable to keep track of the result
        int result = 0;
        
        // create a variable to keep track of the current power of 2
        int powerOf2 = 1;
        
        // create a variable to keep track of the current node
        ListNode curr = head;
        
        // while the current node is not null
        while (curr != null) {
            // if the current node's value is 1
            if (curr.val == 1) {
                // add 2^powerOf2 to the result
                result += Math.pow(2, powerOf2);
            }
            
            // increment powerOf2
            powerOf2++;
            
            // move to the next node
            curr = curr.next;
        }
        
        // return the result
        return result;
    }
}

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        # create an empty string to store the binary number
        binary_string = ""
        
        # iterate through the linked list and add each node's value to the string
        while head:
            binary_string += str(head.val)
            head = head.next
        
        # convert the string to an integer and return it
        return int(binary_string, 2)

/**
 * 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) {
    // create a variable to store the result
    let result = 0;
    
    // create a variable to keep track of the power of 2
    let power = 0;
    
    // create a variable to store the current node
    let curr = head;
    
    // iterate through the list
    while (curr) {
        // if the current node's value is 1
        if (curr.val === 1) {
            // add 2^power to the result
            result += 2 ** power;
        }
        
        // increment power
        power++;
        
        // move to the next node
        curr = curr.next;
    }
    
    // return the result
    return result;
};

/**
 * 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 result = 0;
        while (head) {
            result = result * 2 + head->val;
            head = head->next;
        }
        return result;
    }
};

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public int GetDecimalValue(ListNode head) {
        
        // Create a new variable to store the decimal value
        int decimalValue = 0;
        
        // While there is still a node in the linked list
        while (head != null) {
            
            // Add the current node's value to the decimal value
            decimalValue = decimalValue * 2 + head.val;
            
            // Move on to the next node
            head = head.next;
        }
        
        // Return the decimal value
        return decimalValue;
    }
}