[LeetCode] #1290 Convert Binary Number in a Linked List to Integer (repeat : 0)

LinkedList의 노드에는 이진수로만 이루어져있으며, 이를 십진수로 바꾸는 문제이다. 

 

 

Description 

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.

 

Example 1:

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

Example 2:

Input: head = [0]
Output: 0

 

Solution 

class Solution {
    public int getDecimalValue(ListNode head) {
        int num = 0; // store the decimal number
        ListNode current = head; // pointer node to points the head(first) of the linkedlist
        
        while(current != null){ // iterates the linkedlist as long as current node is not null
            
            // num will get doubled as nums of the nodes in the linkedlist
            // this will build the binary number into decimal equivalent
            // current.val is value of current node . each node corresponds one digit of binary number
            num = num*2 + current.val;
            
            current = current.next;
        }
        
        return num;
    }
}

 

Binary numbers have digits that are either 0 or 1. Since current.value is always either 0 or 1, adding it may not always be necessary. The role of the code num = num * 2 + current.value; is to accumulate the value corresponding to each digit's position, which is a power of 2. However, because the value is always 0 or 1, adding it is sufficient in the current code.

For instance, if current.value is always 0, the effect on num would be equivalent to multiplying it by 2. On the other hand, if current.value is always 1, the effect would be to multiply num by 2 and add 1. By accumulating these values for each binary digit, the code effectively converts the binary number to its decimal equivalent.

In summary, current.value represents the value (either 0 or 1) of the current binary digit, and num accumulates the corresponding power of 2 for each digit, allowing the conversion from binary to decimal.

 

 

 

In terms of time complexity , it is O(n) where n represents the number of nodes in the linked list 

the space complexity is O(1) , constant running time indicating that the amount of memory used by the algorithm remains constant regardless of the size of the input. the algorithm uses only constant number of variables ,, num and current