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 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6class Solution:
7 def getDecimalValue(self, head: ListNode) -> int:
8 result = 0
9 while head:
10 result = (result << 1) | head.val
11 head = head.next
12 return resultThe Python getDecimalValue function iterates through the linked list, constructing the decimal integer by shifting and OR-ing values from each node.
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.
1#include <stdlib.h>
2#include <math.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9int getDecimalValue(struct ListNode* head) {
10 int count = 0;
11 struct ListNode* current = head;
12 while (current != NULL) {
13 count++;
14 current = current->next;
15 }
16 int result = 0;
17 current = head;
18 while (current != NULL) {
19 result += current->val * pow(2, --count);
20 current = current->next;
21 }
22 return result;
23}In this implementation, we traverse the list to calculate the length, which aids in determining the highest power of two needed. A second pass through the list allows for calculation of the decimal value, multiplying each node value by 2 raised to the correct power.