[notes for question brushing] binary linked list to integer

subject ：

Give you a single chain table reference node  head. The value of each node in the list is not 0 Namely 1. It is known that this list is a binary representation of an integer number .

Please go back to the Decimal value .

Example 1：

Input ：head = [1,0,1]
Output ：5
explain ： Binary number (101) Convert to decimal (5)
Example 2：

Input ：head = [0]
Output ：0
Example 3：

Input ：head = [1]
Output ：1
Example 4：

Input ：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
Output ：18880
Example 5：

Input ：head = [0,0]
Output ：0
 

Tips ：

Link list is not empty .
The total number of nodes in the list does not exceed  30.
The value of each node is not  0 Namely 1.

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/convert-binary-number-in-a-linked-list-to-integer

solution ：

        First of all, this single linked list stores binary numbers . If you want to take out every bit of binary, you need to traverse the linked list .

        Ordinary thinking is to traverse it first and record how many bits there are , Then each round is stored in an array , Then use the number of bits of each bit （2^(n - 1)） Multiply by this number and add to get . But this is not only inefficient , And the array is easy to cross the boundary and this n Poorly controlled factors .

        that , We can use decimal numbers in turn to think about ： For example, in an array, each subscript stores an integer of one bit （0~9）, such as int a[] = {1, 2, 3, 9, 2} So let's think about how to make it into a number, that is 12392 Well ？

        Multiplicative multiplication The role of the . For example, the first time I got 1, So first come in and put the first 0 multiply 10, And then add , That is to say, increase the original to one decimal , Become one higher than the number that comes in now , The low position is 0 了 , You can directly add , And then, in turn , You can find that the problem can be solved by using one traversal perfectly .

        Binary isomorphism , Only binary is full two into one , So multiply by 2 that will do .

The code is as follows ：

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

         however , The first thing we should think of is that it is a binary number , What is most relevant to binary numbers is bit operation , So how to say that there is no bit operation ！？

        You can follow the above steps , Move the original number one bit to the left each time , There will be one more on the far right 0, Then press the bit or 1 Namely 1 Otherwise, it would be 0 that will do .

// Binary system  --  An operator 
int getDecimalValue(struct ListNode* head){
    int num = 0;
    struct ListNode* temp = head;
    while(temp)
    {
        num <<= 1;
        num |= temp->val;
        temp = temp->next;
    }
    return num;
}

        Think clearly about the logic of each step .