C++单链表实现：合并、排序、反转及求交并集

C++单链表实现：合并、排序、反转及求交并集

本文提供一份完整的C++代码，用于实现单链表的创建、插入节点、合并、排序、反转、求交集和并集等操作，并附带详细的代码解释。cpp#include using namespace std;

// 定义单链表节点struct ListNode { int val; ListNode* next; ListNode(int value): val(value), next(nullptr) {}};

// 定义插入节点函数ListNode* insertNode(ListNode* head, int value) { ListNode* newNode = new ListNode(value); if (head == nullptr || value >= head->val) { newNode->next = head; return newNode; } else { ListNode* cur = head; while (cur->next != nullptr && cur->next->val > value) { cur = cur->next; } newNode->next = cur->next; cur->next = newNode; return head; }}

// 打印链表void printList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { cout << cur->val << ' '; cur = cur->next; } cout << endl;}

// 创建链表ListNode* createList(int n) { ListNode* head = nullptr; ListNode* cur = nullptr; for (int i = 0; i < n; i++) { int num; cin >> num; ListNode* newNode = new ListNode(num); if (head == nullptr) { head = newNode; cur = head; } else { cur->next = newNode; cur = cur->next; } } return head;}

// 释放链表内存void freeList(ListNode* head) { ListNode* cur = head; while (cur != nullptr) { ListNode* temp = cur; cur = cur->next; delete temp; }}

// 获取链表长度int getLength(ListNode* head) { int length = 0; ListNode* cur = head; while (cur != nullptr) { length++; cur = cur->next; } return length;}

// 获取链表倒数第n个节点ListNode* getNthFromEnd(ListNode* head, int n) { int length = getLength(head); int targetIndex = length - n; ListNode* cur = head; for (int i = 0; i < targetIndex; i++) { cur = cur->next; } return cur;}

// 反转链表ListNode* reverseList(ListNode* head) { ListNode* prev = nullptr; ListNode* cur = head; while (cur != nullptr) { ListNode* nextNode = cur->next; cur->next = prev; prev = cur; cur = nextNode; } return prev;}

// 合并两个有序链表为一个有序链表（从大到小排序）ListNode* mergeTwoLists(ListNode* a, ListNode* b) { ListNode* dummy = new ListNode(0); ListNode* cur = dummy; while (a != nullptr && b != nullptr) { if (a->val >= b->val) { cur->next = a; a = a->next; } else { cur->next = b; b = b->next; } cur = cur->next; } if (a != nullptr) { cur->next = a; } if (b != nullptr) { cur->next = b; } return dummy->next;}

// 复制链表ListNode* copyList(ListNode* head) { ListNode* dummy = new ListNode(0); ListNode* cur = dummy; while (head != nullptr) { cur->next = new ListNode(head->val); cur = cur->next; cur->next = new ListNode(head->val); cur = cur->next; head = head->next; } return dummy->next;}

int main() { // 创建链表a cout << '请输入5个整数，用空格分隔：' << endl; ListNode* a = createList(5);

// 创建链表b    cout << '请输入5个整数，用空格分隔：' << endl;    ListNode* b = createList(5);

// 输出链表a和b的交集和并集    ListNode* curA = a;    ListNode* curB = b;    ListNode* intersection = nullptr;    ListNode* unionList = nullptr;    ListNode* unionCur = nullptr;    while (curA != nullptr && curB != nullptr) {        if (curA->val == curB->val) {            intersection = insertNode(intersection, curA->val);            unionList = insertNode(unionList, curA->val);            curA = curA->next;            curB = curB->next;        }        else if (curA->val < curB->val) {            unionList = insertNode(unionList, curA->val);            curA = curA->next;        }        else {            unionList = insertNode(unionList, curB->val);            curB = curB->next;        }    }    while (curA != nullptr) {        unionList = insertNode(unionList, curA->val);        curA = curA->next;    }    while (curB != nullptr) {        unionList = insertNode(unionList, curB->val);        curB = curB->next;    }    cout << '链表a和b的交集为：';    printList(intersection);    cout << '链表a和b的并集为：';    printList(unionList);

// 将链表b倒序    ListNode* reversedB = reverseList(b);    cout << '倒序后的链表b为：';    printList(reversedB);

// 将两个有序链表合并成一个有序链表（从大到小排序）    ListNode* merged = mergeTwoLists(a, reversedB);    cout << '合并后的有序链表为：';    printList(merged);

// 复制合并后的链表    ListNode* copied = copyList(merged);    cout << '复制后的链表为：';    printList(copied);

// 释放链表内存    freeList(a);    freeList(b);    freeList(intersection);    freeList(unionList);    freeList(reversedB);    freeList(merged);    freeList(copied);

return 0;}

代码解释:

1. 定义节点结构体 ListNode: 包含数据域 val 和指向下一个节点的指针 next。2. insertNode 函数: 将新节点按值升序插入到链表中。3. printList 函数: 遍历并打印链表的每个节点值。4. createList 函数: 创建一个包含 n 个节点的链表，节点值从用户输入获取。5. freeList 函数: 释放链表占用的内存空间。6. getLength 函数: 获取链表的长度。7. getNthFromEnd 函数: 获取链表倒数第 n 个节点。8. reverseList 函数: 反转链表。9. mergeTwoLists 函数: 将两个有序链表合并成一个有序链表（从大到小排序）。10. copyList 函数: 复制链表。

主函数 main 中的代码演示了如何使用上述函数进行链表操作，包括：

• 创建两个链表 a 和 b。* 求解 a 和 b 的交集和并集。* 反转链表 b。* 将 a 和反转后的 b 合并成一个有序链表。* 复制合并后的链表。* 最后，释放所有链表占用的内存空间。

希望这份代码能够帮助你更好地理解和使用C++单链表！