Linked List | 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.

Linked List에 binary 값이 들어가있고 (0 또는 1), 그 값을 integer값으로 계산하는 조건의 문제이다. 처음에는 O(N)이지만, 실제로는 2N, 그러니까 Loop을 두번 도는 알고리즘을 구현했다. Linked List에서는 Easy 난이도의 문제이다. 

class Solution {
    public int getDecimalValue(ListNode head) {
        int sum = 0;
        int count = 0;
        ListNode curr = head;
        
        while(curr != null) {
            count++;
            curr = curr.next;
        }
        
        curr = head;
        while(curr != null){
            sum += curr.val * Math.pow(2, --count);
            curr = curr.next;
        }
        return sum;
    }
}

* Time Complexity: O(N) : 실제로는 2N

* Space Complexity: O(1): 포인터 하나와 sum, count를 위한 integer만 저장한다.

 

두번의 에러를 만났는데, 하나는 while loop 안에서 curr 포인터의 위치를 다음으로 넘겨주지 않아서 나온 overflow, 그리고, 다른 하나는 pow method를 사용할 때, Math를 붙여줘야하는것이었다. 

 

위의 코드를 설명하자면, 처음에 한번의 Loop에 몇자리의 binary인지 알아내고 숫자를 카운트해서 총 길이의 -1한값부터, $2^{count-1}$의 값을 계산해서, 각 노드의 값으로 곱해주는 전략이었다. curr.val에 들어있는 값이 0 또는 1이기때문에, 자동적으로 0일 경우 0의 값이 계산되어서 sum에 저장되었다. 이 알고리즘도, leetcode에서 100%에 해당하는 속도와 그렇게 크지않은 스페이스를 사용했다는 평가를 받았다. 하지만, 이 풀이 이후, bit-manipulation을 이용한 풀이법이 생각났다.

 

class Solution {
    public int getDecimalValue(ListNode head) {
        int sum = 0;
        while(head != null){
            sum = (sum << 1) | head.val;
            head = head.next;
        }
        return sum;
    }
}

* Time Complexity: O(N) 

* Space Complexity: O(1): sum을 위한 공간만 사용한다.

 

Bit Manipulation을 이용하면 훨씬 더 간단하게 풀 수 있다. 바로 shift (<<)를 이용한 방법이다. 기존에 계산한 값을 전체다 1씩 움직여주면 된다. 예를들어서 1101 이라는 binary값이 있다면,  1 -> 1 -> 0 -> 1 - > NULL 과 같은 Linked List가 주어질것이다 그렇다면, 첫번째 룹은 다음과같이 계산되어진다.

$
sum = 0000\;0000 \\
head.val = 0000\;0001 \\\\

sum = sum << 1\;|\;head.val = 0000\;0000 | 0000\;0001 = 0000\;0001
$

그 다음 loop은? sum의 값이 1칸 이동하면서, 기존의 값에 *2가 되어지고, 그다음 값이 더해진다.

$
sum = 0000\;0001 \\
head.val = 0000\;0001 \\\\
sum = 0000\;0010 | 0000\;0001 = 0000\;0011
$

그리고, 

$
sum = 0000\;0011 \\
head.val = 0000\;0000 \\\\
sum = 0000\;0011 | 0000\;0000 = 0000\;0110
$

마지막으로

$
sum = 0000\;0110 \\
head.val = 0000\;0001 \\\\
sum = 0000\;0011 | 0000\;0000 = 0000\;1101
$

이렇게 1번의 Loop으로 binary값을 계산해낼 수 있다. 이전의 풀이도 0ms으로 빠른 알고리즘이어서 100%의 평가를 받아서 구별하기가 쉽지 않지만, 훨씬 빠른 속도일것이고 (아마 최대 32자리이기 때문에 32번의 loop과 64번의 loop의 속도 차이를 측정하기 힘들 것 같다), 전보다 간결해진 코드로, (curr를 복사하는 대신 head를 움직여서 썼고, count를 쓰지 않았다) 메모리도 덜 사용했다. 

 

두 해법 모두 합쳐서 15분정도 걸렸다. 코딩 인터뷰에서 warm up 문제정도의 난이도였다.

 

피카츄가 Linked List에서 1과 0을 나타내기위해 한마리는 서있고 한마리는 앉아있다. 나머지 피카츄는 아직 리스트에 들어오지않고 대기중...

 

Reference

Convert Binary Number in a Linked List to Integer - LeetCode