Leetcode - 1290. Convert Binary Number in a Linked List to Integer

想法:

先將該 linked list 做 reverse 

然後再從尾巴尋訪回來計算數字

(計算方式:

每個 binary 的 digit 要轉成 decimal 的方式為 * 2 的某次方

所以從最小的 digit 開始尋訪並每次遞增 count

pow(a,b) 的結果為 a 的 b 次方

因此 pow(2,count) 會回傳 2 的 count 次方)

Code:

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

typedef struct ListNode Node;

int getDecimalValue(Node* head){

    Node* cur;

    Node* pre;

    Node* tail;

    int count = 0;

    int dec_value = 0;

   

    cur = head;

    tail = cur->next;

    cur->next = NULL;

    pre = cur;

    cur = tail;

    while(tail){

        tail = tail->next;

        cur->next = pre;

        pre = cur;

        cur = tail;

    }

    cur = pre;

    while(cur){

        dec_value += cur->val * pow(2, count);

        count++;

        cur = cur->next;

    }

    return dec_value;

}

更好的解法:

其實不用做 reverse linked list

每次尋訪到新的點可以想成是往最右邊加上一個 bit

因此只須把當前的累積值左移1位(也就是乘2)

再加上當下掃到的值即可(最小的 bit 表示的是 2 的 0 次方)

Code:

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     struct ListNode *next;

 * };

 */

typedef struct ListNode Node;

int getDecimalValue(Node* head){

    Node* cur = head;

    int dec_value = 0;

   

    while(cur){

        dec_value = dec_value * 2 + cur->val;

        cur = cur->next;

    }

    return dec_value;

}

Ref: [LeetCode] 1290. Convert Binary Number in a Linked List to Integer 二进制链表转整数