數據結構基礎（九）：鏈表串接、反轉與打印完整實現

鏈表串接

將第二條鏈表所有節點接到第一條鏈表末尾。關鍵點：必須 深拷貝 第二條鏈表的節點數據，不能直接鏈接原節點，否則析構時會雙重釋放同一記憶體。

void concatenate(const MyList& other) {
    if (isEmpty()) { first = other.first; return; }
    if (other.isEmpty()) return;
    Node* tail = first->next;
    while (tail->next) tail = tail->next;
    for (Node* p = other.first->next; p; p = p->next) {
        tail->next = new Node(p->data);
        tail = tail->next;
    }
}

鏈表反轉

迭代法三指針：`prev`（已反轉部分頭）、`curr`（當前）、`next`（暫存下一個）。逐個反轉 `next` 指針，最後更新頭節點指向 `prev`。

void invert() {
    if (isEmpty()) return;
    Node *prev = nullptr, *curr = first->next;
    while (curr) {
        Node* next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    first->next = prev;
}

鏈表打印（運算符重載）

重載 `operator<<` 遍歷輸出，格式 `a -> b -> c`，便於調試。

ostream& operator<<(ostream& os, const MyList& list) {
    for (Node* p = list.first->next; p; p = p->next) {
        os << p->data;
        if (p->next) os << " -> ";
    }
    return os;
}

測試驗證

主函數構造 int/char/double 鏈表，測試串接、反轉、刪除、打印，輸出符合預期。

總結

模板化鏈表實現了核心操作，強調深拷貝避免記憶體錯誤，代碼結構清晰，適合教學與面試參考。