This approach involves traversing the linked list and building the decimal value using bit manipulation. As the linked list is traversed, the current result is shifted left by one bit (equivalent to multiplying by 2), and the current node's value is added using the OR operation.
Time Complexity: O(n), where n is the number of nodes in the linked list.
Space Complexity: O(1), as we only use a constant amount of additional space.
1class ListNode {
2 int val;
3 ListNode next;
4 ListNode(int x) { val = x; }
5}
6
7class Solution {
8 public int getDecimalValue(ListNode head) {
9 int result = 0;
10 while (head != null) {
11 result = (result << 1) | head.val;
12 head = head.next;
13 }
14 return result;
15 }
16}The Java method getDecimalValue iterates over the linked list, constructing the final decimal value using bitwise operations to shift the result and incorporate each node's value.
This approach involves traversing the linked list twice. First, to count the nodes (and hence determine the power of two to start with) and second to compute the decimal value by iterating through the list again, multiplying each binary digit by the appropriate power of two.
Time Complexity: O(n), where n is the number of nodes, but involves two passes.
Space Complexity: O(1), since it uses constant space plus a few variables.
1class ListNode {
2 int val;
3 ListNode next;
4 ListNode(int x) { val = x; }
5}
6
7class Solution {
8 public int getDecimalValue(ListNode head) {
9 int len = 0, result = 0;
10 ListNode current = head;
11 while (current != null) {
12 len++;
13 current = current.next;
14 }
15 current = head;
16 while (current != null) {
17 result += current.val * Math.pow(2, --len);
18 current = current.next;
19 }
20 return result;
21 }
22}The Java solution first determines the length of the list, then iterates again while computing the decimal value by multiplying each bit by its position's power of two.