แปลง Binary Number ใน Linked List เป็น Integer ใน C++

โจทย์ปัญหา

ได้รับ Singly Linked List ที่แต่ละโหนดมีค่า 0 หรือ 1 แทน Binary Number (MSB First) ให้คืนค่า Decimal Value

ตัวอย่าง

Input: 1 → 0 → 1 → 1 → 0 → 1
Binary: 101101
Output: 45 (32+8+4+1)

แนวคิดการแก้ปัญหา

วิธีที่ 1: Two Pass (Array + Reverse)

1. เดิน List เก็บค่าลง Vector
2. Reverse Vector (LSB First)
3. คำนวณ: ans += bit * (1 << i)

วิธีที่ 2: One Pass (Bit Shift) - แนะนำ

1. result = 0
2. เดิน List: result = (result << 1) | node->val
3. คืนค่า result

โค้ดตัวอย่าง (C++) - ทั้งสองวิธี

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    // Method 1: Two Pass with Vector
    int getDecimalValue_Vector(ListNode* head) {
        vector<int> bits;
        while (head) {
            bits.push_back(head->val);
            head = head->next;
        }
        reverse(bits.begin(), bits.end());

        int ans = 0, pow = 1;
        for (int bit : bits) {
            ans += bit * pow;
            pow <<= 1;
        }
        return ans;
    }

    // Method 2: One Pass Bit Shifting (Optimal)
    int getDecimalValue(ListNode* head) {
        int result = 0;
        while (head) {
            result = (result << 1) | head->val;
            head = head->next;
        }
        return result;
    }
};

// Helper
ListNode* createList(initializer_list<int> vals) {
    ListNode dummy(0), *tail = &dummy;
    for (int v : vals) tail = tail->next = new ListNode(v);
    return dummy.next;
}

int main() {
    Solution sol;
    ListNode* head = createList({1,0,1,1,0,1});
    cout << "Method 1: " << sol.getDecimalValue_Vector(head) << endl;
    head = createList({1,0,1,1,0,1});
    cout << "Method 2: " << sol.getDecimalValue(head) << endl;

    // More tests
    cout << sol.getDecimalValue(createList({0})) << endl;       // 0
    cout << sol.getDecimalValue(createList({1})) << endl;       // 1
    cout << sol.getDecimalValue(createList({1,0,0,0})) << endl; // 8
    return 0;
}

ผลลัพธ์

Method 1: 45
Method 2: 45
0
1
8

Complexity Analysis

คำอธิบายเพิ่มเติม

• วิธี Bit Shift ใช้หลักการ: Binary = (((b₁×2 + b₂)×2 + b₃)×2 + ...)
• เหมือน Horner's Method สำหรับ Polynomial Evaluation
• ระวัง Overflow: ใช้ long long ถ้าระบบ 64-bit และ List ยาว
• LeetCode Problem: #1290

ตัวอย่าง Step-by-Step (101101)

Start: result = 0
1: result = (0<<1) | 1 = 1
0: result = (1<<1) | 0 = 2
1: result = (2<<1) | 1 = 5
1: result = (5<<1) | 1 = 11
0: result = (11<<1) | 0 = 22
1: result = (22<<1) | 1 = 45 ✓