1290. 二进制链表转整数

[GpingFeng]

1290. 二进制链表转整数

解题思路

• 反转链表
• 遍历链表，对应的位置下边值为 2^i
• 返回和

var getDecimalValue = function(head) {
  // 反转一次链表
  let prev = null;
  let cur = head;
  while(cur) {
    [prev, cur.next, cur] = [cur, prev, cur.next]
  }
  let i = 0;
  let sum = 0;
  while(prev) {
    if (prev.val) {
      // 有值的时候进行二进制指数运算
      sum += Math.pow(2, i);
    }
    prev = prev.next;
    i++;
  }
  return sum;
};

复杂度分析

• 时间复杂度——O(n)
• 空间复杂度——O(1)

[GpingFeng]

解法二

其实从开始遍历到结束也是可以做到的

var getDecimalValue = function(head) {
  let sum = 0;
  while(head) {
    sum = sum * 2 + head.val;
    head = head.next;
  }
  return sum;
};