1290. Convert Binary Number in a Linked List to Integer

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

Constraints:

• The Linked List is not empty.
• Number of nodes will not exceed 30.
• Each node’s value is either 0 or 1.

Follow up: Note: This question is the same as 번호.제목

💡 Hint 1:
Traverse the linked list and store all values in a string or array. convert the values obtained to decimal value.

💡 Hint 2:
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.

Submitted Code

# 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: Optional[ListNode]) -> int:
        result = 0
        
        while head:
            result <<= 1        # 비트를 왼쪽으로 밀어서 마지막 자리 확보
            result |= head.val  # 마지막 자리에 현재 값 넣기
            head = head.next

        return result

Runtime: 0 ms | Beats 100.00%
Memory: 19.35 MB | Beats 14.40%

리스트를 순회하며 발견한 값을 문자열로 저장해도 되지만, 비트를 누적시키는 방법을 사용하면 O(1) 메모리만 사용하여 풀 수 있다.

Other Solutions

1st

class Solution:
    def getDecimalValue(self, head: ListNode) -> int:
        answer = 0
        while head: 
            answer = 2*answer + head.val 
            head = head.next 
        return answer 

time complexity: 𝑂(𝑛)
space complexity: 𝑂(1)

비트 연산 대신 사칙연산으로 계산해도 같은 결과가 나온다.