Given a singly linked list of 0s and 1s find its decimal equivalent.
Input: 0->0->0->1->1->0->0->1->0 Output: 50 Input: 1->0->0 Output: 4
The decimal value of an empty linked list is considered as 0.
Initialize the result as 0. Traverse the linked list and for each node, multiply the result by 2 and add the node’s data to it.
Javascript
<script>// Javascript Program to find decimal value // of binary linked list // Link list Nodeclass Node { constructor() { this.data = true; this.next = null; }}// Returns decimal value of binary // linked list function decimalValue(head) { // Initialized result var res = 0; // Traverse linked list while (head != null) { // Multiply result by 2 and add // head's data res = (res << 1) + (head.data ? 1 : 0); // Move next head = head.next; } return res;}// Utility function to create a // new node.function newNode(data) { var temp = new Node(); temp.data = (data == 1 ? true : false); temp.next = null; return temp;}// Driver code // Start with the empty list var head = newNode(1);head.next = newNode(0);head.next.next = newNode(1);head.next.next.next = newNode(1);document.write("Decimal value is " + decimalValue(head));// This code is contributed by aashish1995 </script> |
Output :
Decimal value is 11
Time Complexity: O(n) where n is the number of nodes in the given linked list.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Another Approach(by reversing the Linked List):
Follow the below steps to solve the given problem
1) First reverse the given linked list.
2) Initialize a ans variable to store ans and pos variable to keep track of position of node in linked list.
3) Perform the operation ans = ans + (rhead.data*(2**pos))%MOD)
4) perform ans = ans%MOD
Below is the implementation of above approach:
Javascript
// JavaScript program to find the decimal value// of binary linked list// node classclass Node{ constructor(data){ this.data = data; this.left = null; this.right = null; }}function reverse(head){ if(head == null || head.next == null) return head; let curr = head; let prev = null; let nxt = head.next; while(nxt != null){ curr.next = prev; prev = curr; curr = nxt; nxt = nxt.next; } curr.next = prev; return curr;}function decimalValue(head){ let MOD = 1000000007; let rhead = reverse(head); let ans = 0; let pos = 0; while(rhead != null){ ans = (ans % MOD+(rhead.data*(2**pos)) % MOD) % MOD; rhead = rhead.next; pos += 1; } return ans;}// driver program to test above functionlet head = new Node(1);head.next = new Node(0);head.next.next = new Node(1);head.next.next.next= new Node(1);console.log("Decimal Value is : " + decimalValue(head)); |
Decimal Value is : 11
Time Complexity: O(N) where N is the number of nodes in linked list.
Auxiliary Space: O(1)
Please refer complete article on Decimal Equivalent of Binary Linked List for more details!
