1290. Convert Binary Number in a Linked List to Integer

發表於 | 分類於

problem

solution

option 1 - recursive

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int ret = 0;
    void preorder(ListNode * head){
        if(!head) return ;
        ret<<=1;
        ret+=head->val;
        preorder(head->next);
    }
    int getDecimalValue(ListNode* head) {
        preorder(head);
        return ret;
    }
};

option 2 - iterative

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        int sum = 0;
        for(;head;head=head->next){
            sum<<=1;
            sum+=head->val;
        }
        return sum;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)