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:

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

Example 2:

1Input: head = [0]
2Output: 0

Example 3:

1Input: head = [1,1,0,1]
2Output: 13

Constraints:

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

Solution

Simple Approach

The problem is about iterating through the list and using the binary numbers to multiply by 2.

 1class Solution {
 2    public int getDecimalValue(ListNode head) {
 3        int result = 0;
 4        while (head != null) {
 5            result = result * 2 + head.val;
 6            head = head.next;
 7        }
 8        return result;
 9    }
10}
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Using Bit Manipulations

 1class Solution {
 2    public int getDecimalValue (ListNode head) {
 3        int result = 0;
 4        while (head != null) {
 5            result = (result << 1) | head.val;
 6            head = head.next;
 7        }
 8        return result;
 9    }
10}
  • Time Complexity: O(n)
  • Space Complexity: O(1)