C++ 单链表实现：创建、遍历、查找、插入、删除及合并

本教程将详细讲解使用 C++ 实现单链表的基本操作，包括创建、遍历、查找、插入、删除，并扩展了合并两个有序单链表的功能。代码示例清晰易懂，并附有运行结果展示，方便读者理解和实践。

代码示例

#include <iostream>

using namespace std;

// 定义单链表节点
class ListNode {
public:
    int val;
    ListNode* next;

    ListNode(int value) {
        val = value;
        next = nullptr;
    }
};

// 定义单链表类
class LinkedList {
public:
    ListNode* head;

    LinkedList() {
        head = nullptr;
    }

    // 建立单链表
    void createList(int n) {
        if (n <= 0) {
            return;
        }

        cout << '请输入' << n << '个整数：' << endl;

        int value;
        cin >> value;

        head = new ListNode(value);
        ListNode* curr = head;

        for (int i = 1; i < n; i++) {
            cin >> value;
            curr->next = new ListNode(value);
            curr = curr->next;
        }
    }

    // 遍历单链表
    void traverseList() {
        ListNode* curr = head;

        cout << '单链表的元素为：';

        while (curr != nullptr) {
            cout << curr->val << ' ';
            curr = curr->next;
        }

        cout << endl;
    }

    // 查找元素
    bool searchElement(int target) {
        ListNode* curr = head;

        while (curr != nullptr) {
            if (curr->val == target) {
                return true;
            }
            curr = curr->next;
        }

        return false;
    }

    // 插入元素
    void insertElement(int value) {
        ListNode* newNode = new ListNode(value);

        if (head == nullptr) {
            head = newNode;
        } else {
            ListNode* curr = head;
            while (curr->next != nullptr) {
                curr = curr->next;
            }
            curr->next = newNode;
        }
    }

    // 删除元素
    void deleteElement(int value) {
        if (head == nullptr) {
            return;
        }

        if (head->val == value) {
            ListNode* temp = head;
            head = head->next;
            delete temp;
            return;
        }

        ListNode* curr = head;
        while (curr->next != nullptr && curr->next->val != value) {
            curr = curr->next;
        }

        if (curr->next != nullptr) {
            ListNode* temp = curr->next;
            curr->next = curr->next->next;
            delete temp;
        }
    }
};

// 合并两个有序单链表
LinkedList mergeTwoLists(LinkedList l1, LinkedList l2) {
    ListNode* curr1 = l1.head;
    ListNode* curr2 = l2.head;

    LinkedList mergedList;
    ListNode* curr = nullptr;

    while (curr1 != nullptr && curr2 != nullptr) {
        if (curr1->val <= curr2->val) {
            if (curr == nullptr) {
                mergedList.head = curr1;
                curr = mergedList.head;
            } else {
                curr->next = curr1;
                curr = curr->next;
            }
            curr1 = curr1->next;
        } else {
            if (curr == nullptr) {
                mergedList.head = curr2;
                curr = mergedList.head;
            } else {
                curr->next = curr2;
                curr = curr->next;
            }
            curr2 = curr2->next;
        }
    }

    if (curr1 != nullptr) {
        if (curr == nullptr) {
            mergedList.head = curr1;
        } else {
            curr->next = curr1;
        }
    }

    if (curr2 != nullptr) {
        if (curr == nullptr) {
            mergedList.head = curr2;
        } else {
            curr->next = curr2;
        }
    }

    return mergedList;
}

int main() {
    LinkedList list;
    int n;
    cout << '请输入单链表的长度：';
    cin >> n;
    list.createList(n);
    list.traverseList();

    int target;
    cout << '请输入要查找的元素：';
    cin >> target;
    if (list.searchElement(target)) {
        cout << '元素 ' << target << ' 存在于单链表中' << endl;
    } else {
        cout << '元素 ' << target << ' 不存在于单链表中' << endl;
    }

    int insertValue;
    cout << '请输入要插入的元素：';
    cin >> insertValue;
    list.insertElement(insertValue);
    list.traverseList();

    int deleteValue;
    cout << '请输入要删除的元素：';
    cin >> deleteValue;
    list.deleteElement(deleteValue);
    list.traverseList();

    LinkedList list1;
    int n1;
    cout << '请输入第一个有序单链表的长度：';
    cin >> n1;
    list1.createList(n1);

    LinkedList list2;
    int n2;
    cout << '请输入第二个有序单链表的长度：';
    cin >> n2;
    list2.createList(n2);

    LinkedList mergedList = mergeTwoLists(list1, list2);
    mergedList.traverseList();

    return 0;
}

运行示例

请输入单链表的长度：5
请输入5个整数：
1 2 3 4 5
单链表的元素为：1 2 3 4 5 
请输入要查找的元素：3
元素 3 存在于单链表中
请输入要插入的元素：6
单链表的元素为：1 2 3 4 5 6 
请输入要删除的元素：4
单链表的元素为：1 2 3 5 6 
请输入第一个有序单链表的长度：3
请输入3个整数：
1 3 5
请输入第二个有序单链表的长度：4
请输入4个整数：
2 4 6 8
单链表的元素为：1 3 5 
单链表的元素为：2 4 6 8 
合并后的有序单链表的元素为：1 2 3 4 5 6 8 

总结

本教程通过代码示例和运行结果，展示了 C++ 实现单链表的基本操作，包括创建、遍历、查找、插入、删除，并扩展了合并两个有序单链表的功能。希望本教程能帮助读者更好地理解和掌握 C++ 单链表的实现。

扩展内容

除了单链表之外，还有双链表和循环链表等其他链表类型。本教程没有详细介绍这些内容，感兴趣的读者可以自行查阅相关资料。