1、实现线性表的链式存储定义，完成单链表的创建、插入、删除、查找等常用操作， 将线性链表逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点， 以此类推。 2、利用链表的插入用算法建立线性链表，然后利用链表的查找，删除、计数、输出等 运算反复实现链表的这些操作（插入、删除、查找、计数、输出单独写成函数的形式），并 能在屏幕上输出操作前后的结果。要求 计算 C(x) = A(x)+B(x)，结果存到单链表 hc 中。

1. 单链表的创建、插入、删除、查找等操作实现

#include <iostream>

using namespace std;

// 定义链表结点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 创建链表
ListNode* createList(int a[], int n) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int i = 0; i < n; i++) {
        ListNode* node = new ListNode(a[i]);
        cur->next = node;
        cur = cur->next;
    }
    return dummy->next;
}

// 插入结点
ListNode* insertNode(ListNode* head, int pos, int val) {
    if (pos < 0) return head;
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* prev = dummy;
    while (pos > 0 && prev->next) {
        prev = prev->next;
        pos--;
    }
    if (pos != 0) return head;
    ListNode* node = new ListNode(val);
    node->next = prev->next;
    prev->next = node;
    return dummy->next;
}

// 删除结点
ListNode* deleteNode(ListNode* head, int val) {
    if (!head) return NULL;
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* prev = dummy;
    while (prev->next && prev->next->val != val) {
        prev = prev->next;
    }
    if (prev->next && prev->next->val == val) {
        ListNode* tmp = prev->next;
        prev->next = prev->next->next;
        delete tmp;
    }
    return dummy->next;
}

// 查找结点
ListNode* searchNode(ListNode* head, int val) {
    ListNode* cur = head;
    while (cur && cur->val != val) {
        cur = cur->next;
    }
    return cur;
}

// 逆置链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    while (head) {
        ListNode* tmp = head->next;
        head->next = prev;
        prev = head;
        head = tmp;
    }
    return prev;
}

// 输出链表
void printList(ListNode* head) {
    ListNode* cur = head;
    while (cur) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

int main() {
    int a[] = {1, 2, 3, 4, 5};
    int n = sizeof(a) / sizeof(int);
    ListNode* head = createList(a, n);
    printList(head); // 1 2 3 4 5

    // 插入结点
    head = insertNode(head, 2, 6);
    printList(head); // 1 2 6 3 4 5

    // 删除结点
    head = deleteNode(head, 3);
    printList(head); // 1 2 6 4 5

    // 查找结点
    ListNode* node = searchNode(head, 2);
    if (node) {
        cout << "Found: " << node->val << endl; // Found: 2
    } else {
        cout << "Not Found" << endl;
    }

    // 逆置链表
    head = reverseList(head);
    printList(head); // 5 4 6 2 1

    return 0;
}

2. 利用链表的插入用算法建立线性链表，并实现反复操作

#include <iostream>

using namespace std;

// 定义链表结点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 创建链表
ListNode* createList(int a[], int n) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    for (int i = 0; i < n; i++) {
        ListNode* node = new ListNode(a[i]);
        cur->next = node;
        cur = cur->next;
    }
    return dummy->next;
}

// 插入结点
ListNode* insertNode(ListNode* head, int pos, int val) {
    if (pos < 0) return head;
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* prev = dummy;
    while (pos > 0 && prev->next) {
        prev = prev->next;
        pos--;
    }
    if (pos != 0) return head;
    ListNode* node = new ListNode(val);
    node->next = prev->next;
    prev->next = node;
    return dummy->next;
}

// 删除结点
ListNode* deleteNode(ListNode* head, int val) {
    if (!head) return NULL;
    ListNode* dummy = new ListNode(-1);
    dummy->next = head;
    ListNode* prev = dummy;
    while (prev->next && prev->next->val != val) {
        prev = prev->next;
    }
    if (prev->next && prev->next->val == val) {
        ListNode* tmp = prev->next;
        prev->next = prev->next->next;
        delete tmp;
    }
    return dummy->next;
}

// 查找结点
ListNode* searchNode(ListNode* head, int val) {
    ListNode* cur = head;
    while (cur && cur->val != val) {
        cur = cur->next;
    }
    return cur;
}

// 逆置链表
ListNode* reverseList(ListNode* head) {
    ListNode* prev = NULL;
    while (head) {
        ListNode* tmp = head->next;
        head->next = prev;
        prev = head;
        head = tmp;
    }
    return prev;
}

// 计数结点
int countNode(ListNode* head) {
    int count = 0;
    ListNode* cur = head;
    while (cur) {
        count++;
        cur = cur->next;
    }
    return count;
}

// 输出链表
void printList(ListNode* head) {
    ListNode* cur = head;
    while (cur) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;
}

// 计算 C(x) = A(x) + B(x)
ListNode* addList(ListNode* head1, ListNode* head2) {
    ListNode* dummy = new ListNode(-1);
    ListNode* cur = dummy;
    int carry = 0; // 进位
    while (head1 || head2 || carry) {
        int sum = carry;
        if (head1) {
            sum += head1->val;
            head1 = head1->next;
        }
        if (head2) {
            sum += head2->val;
            head2 = head2->next;
        }
        carry = sum / 10;
        ListNode* node = new ListNode(sum % 10);
        cur->next = node;
        cur = cur->next;
    }
    return dummy->next;
}

int main() {
    int a[] = {1, 2, 3};
    int n = sizeof(a) / sizeof(int);
    ListNode* head = createList(a, n);
    printList(head); // 1 2 3

    // 反复插入、删除、查找、计数、输出链表
    head = insertNode(head, 2, 4);
    printList(head); // 1 2 4 3
    head = deleteNode(head, 2);
    printList(head); // 1 4 3
    ListNode* node = searchNode(head, 4);
    if (node) {
        cout << "Found: " << node->val << endl; // Found: 4
    } else {
        cout << "Not Found" << endl;
    }
    cout << "Count: " << countNode(head) << endl; // Count: 3
    head = insertNode(head, 3, 5);
    printList(head); // 1 4 3 5

    // 逆置链表
    head = reverseList(head);
    printList(head); // 5 3 4 1

    // 计算 C(x) = A(x) + B(x)
    int b[] = {9, 8, 7};
    n = sizeof(b) / sizeof(int);
    ListNode* head1 = createList(a, n);
    ListNode* head2 = createList(b, n);
    printList(head1); // 1 2 3
    printList(head2); // 9 8 7
    ListNode* hc = addList(head1, head2);
    printList(hc); // 0 1 1 1

    return 0;
}