Convert Binary Number In A Linked List To Integer - Leetcode Solution

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.

1