C++ 經典筆試題精解：鏈表反轉與 String 類完整實作

編輯：關於C語言

題目一：單向鏈表反轉

目標：將 1→2→3→4→5 反轉為 5→4→3→2→1，原地操作，O(n) 時間，O(1) 空間。

核心邏輯：三指標迭代法

struct Node {
    int data;
    Node* next;
};

void reverse(Node*& head) {
    if (!head) return;
    Node *prev = head;
    Node *curr = head->next;
    while (curr) {
        Node* next = curr->next; // 1. 暫存下一節點
        curr->next = prev;       // 2. 反轉指標
        prev = curr;             // 3. 前移 prev
        curr = next;             // 4. 前移 curr
    }
    head->next = nullptr; // 原頭節點變尾，next 置空
    head = prev;          // 更新頭指標
}

關鍵點

參數用 Node*& 參考傳遞，能修改呼叫端的頭指標。
處理空鏈表、單節點邊界情況。
原頭節點 next 必須置 nullptr，否則形成環。

題目二：String 類完整實作（規則三/五）

類別定義：

class String {
public:
    String(const char* str = nullptr);      // 通用建構函數
    String(const String& other);            // 拷貝建構函數
    ~String();                              // 解構函數
    String& operator=(const String& rhs);   // 拷貝指派運算子
private:
    char* m_data;
};

完整實作

String::String(const char* str) {
    if (!str) {
        m_data = new char[1];
        m_data[0] = '\0';
    } else {
        m_data = new char[strlen(str) + 1];
        strcpy(m_data, str);
    }
}

String::String(const String& other) {
    m_data = new char[strlen(other.m_data) + 1];
    strcpy(m_data, other.m_data);
}

String::~String() {
    delete[] m_data;
}

String& String::operator=(const String& rhs) {
    if (this == &rhs) return *this; // 自我指派檢查
    delete[] m_data;                // 釋放舊資源
    m_data = new char[strlen(rhs.m_data) + 1];
    strcpy(m_data, rhs.m_data);
    return *this;
}

現代 C++ 改進：移動語意 (C++11)

// 移動建構函數
String(String&& other) noexcept : m_data(other.m_data) {
    other.m_data = nullptr;
}

// 移動指派運算子
String& operator=(String&& rhs) noexcept {
    if (this != &rhs) {
        delete[] m_data;
        m_data = rhs.m_data;
        rhs.m_data = nullptr;
    }
    return *this;
}

題目三：位元計數函數 (微軟面試題)

int func(int x) {
    int count = 0;
    while (x) {
        count++;
        x = x & (x - 1); // 清除最低位的 1
    }
    return count;
}
// x = 9999 (二進位 10011100001111) → 8 個 1

原理：x & (x-1) 每次清除最低位的 1，迴圈次數即為 1 的個數（Brian Kernighan 演算法）。