【刷题笔记】二进制链表转整数

题目：

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

示例 1：

输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)
示例 2：

输入：head = [0]
输出：0
示例 3：

输入：head = [1]
输出：1
示例 4：

输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880
示例 5：

输入：head = [0,0]
输出：0
 

提示：

链表不为空。
链表的结点总数不超过 30。
每个结点的值不是 0 就是 1。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/convert-binary-number-in-a-linked-list-to-integer

解法：

        首先说明了此单链表存储的均是二进制数。想要取出每一位二进制那么就需要遍历一遍链表。

        普通的思考就是首先遍历一遍将有多少位记录下来，然后每一轮存入一个数组，然后利用每一位的位数（2^(n - 1)）乘以此数然后相加即可得到。但是这样不仅仅效率低下，而且数组容易越界和这个n控制不好的因素。

        那么，我们可以反过来借用一下十进制的数来思考一下：比如一个数组里面每一个下标存着一个位的整数（0~9），比如int a[] = {1, 2, 3, 9, 2}那么我们来想一下如何将它组成一个数即12392呢？

        累乘的作用就出来了。比如第一次取到的是1，那么首先进来先把最开始的0乘以10，然后加上，即把原来升一个十进制，变成比现在进来的这个数高一位，低位就是0了，就可以直接加了，然后依次进行，就可以发现完美利用了一次遍历就把问题解决。

        二进制同理，只不过二进制是满二进一，所以乘以2即可。

代码如下：

int getDecimalValue(struct ListNode* head){
    int num = 0;
    struct ListNode* temp = head;
    while(temp)
    {
        num = num * 2 + temp->val;
        temp = temp->next;
    }
    return num;
}

        但是，我们首先应该想到的是它是一个二进制数，和二进制数最相关的不就是位运算嘛，那么没有位运算怎么说呢！？

        可以仿照上面的步骤，每一次将原来的数向左移动一位，最右边就会多出一个0，然后进行按位或是1就是1否则就是0即可。

//二进制 -- 位运算符
int getDecimalValue(struct ListNode* head){
    int num = 0;
    struct ListNode* temp = head;
    while(temp)
    {
        num <<= 1;
        num |= temp->val;
        temp = temp->next;
    }
    return num;
}

        要把每一步的逻辑想清楚。