基於模板的 C++ 單鏈表完整實現：增刪查改、倒數第 K 個節點三種解法

節點與鏈表類模板設計

template 
class ListNode {
    friend class List;
    T data;
    ListNode* next;
public:
    ListNode() : next(nullptr) {}
    ListNode(const T& val, ListNode* n = nullptr) : data(val), next(n) {}
};

template 
class List {
    ListNode* head; // 哨兵節點
public:
    List() : head(new ListNode()) {}
    ~List() { clear(); delete head; }
    // ... 核心接口聲明
};

核心操作實現精要

• 插入：找到第 i-1 個節點，修改指針鏈接新節點。
• 刪除：同理定位前驅，跳過目標節點並 delete。
• 查找：遍歷計數，支持按位置或按值查找。
• 清空：反覆刪除首節點直到為空。

經典面試題：倒數第 K 個節點三種解法

解法一：雙指針一次遍歷（最優）

T findKthFromEnd(int k) {
    ListNode *fast = head->next, *slow = head->next;
    while (k-- && fast) fast = fast->next;
    if (!fast) throw out_of_range("k exceeds length");
    while (fast) { fast = fast->next; slow = slow->next; }
    return slow->data;
}

解法二：兩次遍歷（先計長度）

先統計總長度 len，倒數第 k 個即正數第 len-k+1 個，再走一遍。

解法三：遞歸回溯（隱式棧）

ListNode* helper(ListNode* node, int k, int& cnt) {
    if (!node) return nullptr;
    ListNode* res = helper(node->next, k, cnt);
    if (++cnt == k) return node;
    return res;
}

完整測試用例

int main() {
    List lst;
    for (int i = 1; i < 10; ++i) lst.insert(i, i); // 尾插
    lst.show(); // 1->2->...->9
    cout << "4th from end: " << lst.findKthFromEnd(4) << endl; // 6
    lst.removeAll(5);
    lst.show();
    return 0;
}

模板化優勢總結

同一套代碼支持 int、double、string、自定義結構體等任意可拷貝類型，編譯器自動生成專用版本，零運行時開銷。