用c++写 线性表链式存储结构下基本操作的实现（初始化、建表、取值、查找、插入、删除、两个非递减有序链表的归并等

线性表的链式存储结构在 C++ 中通常通过定义节点（Node）结构体来实现，包含数据域和指向下一个节点的指针。以下是基本操作的一些实现：

1. 初始化 (创建链表)

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

// 创建空链表
Node* createList() {
    return nullptr;
}

2. 建表 (插入首元素)

void insertAtStart(Node** head, int value) {
    Node* newNode = new Node();
    newNode->data = value;
    newNode->next = *head;
    *head = newNode;
}

3. 取值 (访问特定位置的数据)

int getValue(Node* node, int index) {
    if (index < 0 || !node) return -1; // 检查索引是否合法
    for (int i = 0; i < index && node != nullptr; ++i) {
        node = node->next;
    }
    return node ? node->data : -1;
}

4. 查找 (定位特定值的位置)

int findValue(Node* head, int value) {
    while (head != nullptr) {
        if (head->data == value) return 0; // 如果找到就返回当前索引
        head = head->next;
    }
    return -1;
}

5. 插入 (在指定位置插入新元素)

void insertAfter(Node** head, int position, int value) {
    if (position <= 0 || !*head) return;
    Node* newNode = new Node();
    newNode->data = value;
    if (position == 0) {
        newNode->next = *head;
        *head = newNode;
    } else {
        Node* current = *head;
        for (int i = 0; i < position - 1 && current->next != nullptr; ++i) {
            current = current->next;
        }
        if (current->next != nullptr) {
            newNode->next = current->next;
            current->next = newNode;
        }
    }
}

6. 删除 (删除某个值或指定位置的节点)

void deleteValue(Node** head, int value) {
    if (!head || !(*head)->data) return;

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

    while (temp->next != nullptr && temp->next->data != value) {
        temp = temp->next;
    }
    if (temp->next != nullptr) {
        temp->next = temp->next->next;
        delete temp->next;
    }
}

void deleteByPosition(Node** head, int position) {
    if (position < 0 || !*head) return;
    if (position == 0) {
        *head = (*head)->next;
        delete *head;
    } else {
        Node* current = *head;
        for (int i = 0; i < position - 1 && current->next != nullptr; ++i) {
            current = current->next;
        }
        if (current->next != nullptr) {
            current->next = current->next->next;
            delete current->next;
        }
    }
}

7. 归并两个非递减有序链表 (合并两个已排序链表)

Node* mergeSortedLists(Node* list1, Node* list2) {
    if (!list1) return list2;
    if (!list2) return list1;

    if (list1->data <= list2->data) {
        list1->next = mergeSortedLists(list1->next, list2);
        return list1;
    } else {
        list2->next = mergeSortedLists(list1, list2->next);
        return list2;
    }
}