Given a single linked list node, representing a binary number with most significant digits first, return it as an integer.
Example 1
Input
node = 1 → 0 → 0
Output
4Explanation
The linked list represented 100 in binary.
Math: Convert Binary to Decimal Integer
The binary converted to decimal can be computed by suming up the digits at each position with the weight. For example (110) in binary = 1*2^2 + 1*2^1 + 0*2^0. We can follow the linked list, and multiply current value by two (shifting one position to the left) and add the value of the current node.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | /** * class LLNode { * public: * int val; * LLNode *next; * }; */ int solve(LLNode* node) { int r = 0; while (node) { r = r * 2 + node->val; node = node->next; } return r; } |
/**
* class LLNode {
* public:
* int val;
* LLNode *next;
* };
*/
int solve(LLNode* node) {
int r = 0;
while (node) {
r = r * 2 + node->val;
node = node->next;
}
return r;
}This takes O(N) time and O(1) space.
–EOF (The Ultimate Computing & Technology Blog) —
GD Star Rating
loading...
199 wordsloading...
Last Post: Algorithms to Compute the SubString with Indexing into an Infinite String
Next Post: Can a String be Constructing by Removing a Letter from Another String?
