單向鏈表八大核心操作 C++ 完整實現

節點定義

struct LinkNode {
    int data;
    LinkNode* next;
    LinkNode(int val = 0) : data(val), next(nullptr) {}
};

操作清單與核心代碼

1. 創建鏈表（尾插法）

LinkNode* createLink(int n) {
    if (n <= 0) return nullptr;
    int val;
    cout << "請輸入第 1 個數字：";
    cin >> val;
    LinkNode* head = new LinkNode(val);
    LinkNode* tail = head;
    for (int i = 1; i < n; ++i) {
        cout << "請輸入第 " << i+1 << " 個數字：";
        cin >> val;
        tail->next = new LinkNode(val);
        tail = tail->next;
    }
    return head;
}

2. 求長度

int lengthLink(LinkNode* head) {
    int cnt = 0;
    for (auto p = head; p; p = p->next) ++cnt;
    return cnt;
}

3. 按值插入（在 key 後插入 data）

LinkNode* insertNode(LinkNode* head, int data, int key) {
    for (auto p = head; p; p = p->next) {
        if (p->data == key) {
            auto s = new LinkNode(data);
            s->next = p->next;
            p->next = s;
            cout << "插入成功\n";
            return head;
        }
    }
    cout << "未找到 key，插入失敗\n";
    return head;
}

4. 按位置刪除（第 num 個節點，1-based）

LinkNode* deleteNode(LinkNode* head, int num) {
    if (!head || num < 1) return head;
    if (num == 1) {
        LinkNode* tmp = head;
        head = head->next;
        delete tmp;
        cout << "刪除頭節點成功\n";
        return head;
    }
    LinkNode* pre = head;
    for (int i = 1; pre && i < num-1; ++i) pre = pre->next;
    if (!pre || !pre->next) { cout << "位置越界\n"; return head; }
    LinkNode* del = pre->next;
    pre->next = del->next;
    delete del;
    cout << "刪除成功\n";
    return head;
}

5. 鏈表排序（交換數據域，冒泡思想）

LinkNode* sortLink(LinkNode* head) {
    for (auto p1 = head; p1; p1 = p1->next)
        for (auto p2 = p1->next; p2; p2 = p2->next)
            if (p1->data > p2->data) swap(p1->data, p2->data);
    return head;
}

6. 鏈表逆序（迭代三指針法）

LinkNode* invertLink(LinkNode* head) {
    LinkNode *pre = nullptr, *cur = head, *nxt;
    while (cur) {
        nxt = cur->next;
        cur->next = pre;
        pre = cur;
        cur = nxt;
    }
    return pre; // 新頭節點
}

7. 遞歸逆序（教學演示）

LinkNode* invertRec(LinkNode* head) {
    if (!head || !head->next) return head;
    LinkNode* newHead = invertRec(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

8. 逆序輸出（遞歸）

void printInverse(LinkNode* head) {
    if (!head) return;
    printInverse(head->next);
    cout << head->data << ' ';
}

9. 查找第 num 個節點

LinkNode* locateN(LinkNode* head, int num) {
    int i = 1;
    for (auto p = head; p; p = p->next, ++i)
        if (i == num) return p;
    return nullptr;
}

10. 打印鏈表

void printLink(LinkNode* head) {
    for (auto p = head; p; p = p->next)
        cout << p->data << ' ';
    cout << '\n';
}

測試主函數

int main() {
    int n; cout << "節點數："; cin >> n;
    LinkNode* L = createLink(n);
    printLink(L);
    cout << "長度：" << lengthLink(L) << '\n';
    L = insertNode(L, 99, 2);
    printLink(L);
    L = deleteNode(L, 3);
    printLink(L);
    L = sortLink(L);
    printLink(L);
    L = invertLink(L);
    printLink(L);
    return 0;
}

記憶體管理提醒

• 所有 new 分配的節點必須在程序結束前 delete，或使用智能指針 unique_ptr 自動管理（C++11+）。
• 遞歸逆序/輸出在極長鏈表下可能棧溢出，生產環境優先用迭代版。