在C++中，链表是一种常见的数据结构。插入排序和删除重复节点是链表操作中较为基础的两个任务。下面分别介绍如何实现这两种操作。
链表节点定义
首先，我们定义链表节点结构：
struct ListNode {int val;ListNode* next;ListNode(int x) : val(x), next(nullptr) {}
};
插入排序
插入排序是通过逐一比较元素并将其插入到正确位置来排序链表。实现步骤如下：
- 创建一个哑节点
dummy，它的下一个节点指向链表头部。 - 遍历链表，将每个节点插入到正确位置。
以下是插入排序的实现代码：
ListNode* insertionSortList(ListNode* head) {if (!head) return nullptr;ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* curr = head;ListNode* prev = dummy;ListNode* next = nullptr;while (curr) {if (curr->next && curr->next->val < curr->val) {// Find the position to insert the next nodenext = curr->next;curr->next = next->next;prev = dummy;// Locate the insertion pointwhile (prev->next && prev->next->val < next->val) {prev = prev->next;}// Insert the nodenext->next = prev->next;prev->next = next;} else {curr = curr->next;}}ListNode* sorted_head = dummy->next;delete dummy;return sorted_head;
}
删除重复节点
删除链表中的重复节点可以分为两种情况：删除所有重复的节点（只保留唯一出现的节点）和只删除重复出现的多余节点（保留一个）。
1. 删除所有重复的节点
ListNode* deleteDuplicatesAll(ListNode* head) {if (!head) return nullptr;ListNode* dummy = new ListNode(0);dummy->next = head;ListNode* prev = dummy;while (head) {bool duplicate = false;while (head->next && head->val == head->next->val) {duplicate = true;head = head->next;}if (duplicate) {head = head->next;continue;}prev->next = head;prev = head;head = head->next;}prev->next = nullptr; // Ensure the last node points to nullptrListNode* unique_head = dummy->next;delete dummy;return unique_head;
}
2. 删除重复出现的多余节点（保留一个）
ListNode* deleteDuplicates(ListNode* head) {if (!head) return nullptr;ListNode* curr = head;while (curr && curr->next) {if (curr->val == curr->next->val) {ListNode* temp = curr->next;curr->next = curr->next->next;delete temp; // Free memory} else {curr = curr->next;}}return head;
}
测试代码
以下是一些简单的测试代码：
void printList(ListNode* head) {while (head) {std::cout << head->val << " -> ";head = head->next;}std::cout << "nullptr" << std::endl;
}int main() {// Create a sample linked list: 4 -> 3 -> 3 -> 2 -> 1 -> nullptrListNode* head = new ListNode(4);head->next = new ListNode(3);head->next->next = new ListNode(3);head->next->next->next = new ListNode(2);head->next->next->next->next = new ListNode(1);std::cout << "Original list:" << std::endl;printList(head);// Perform insertion sorthead = insertionSortList(head);std::cout << "Sorted list:" << std::endl;printList(head);// Delete duplicates, keeping only unique elementshead = deleteDuplicatesAll(head);std::cout << "List after deleting all duplicates:" << std::endl;printList(head);// Create another sample linked list: 1 -> 1 -> 2 -> 3 -> 3 -> nullptrhead = new ListNode(1);head->next = new ListNode(1);head->next->next = new ListNode(2);head->next->next->next = new ListNode(3);head->next->next->next->next = new ListNode(3);std::cout << "Another list with duplicates:" << std::endl;printList(head);// Delete duplicates, keeping one instancehead = deleteDuplicates(head);std::cout << "List after deleting duplicates (keeping one):" << std::endl;printList(head);return 0;
}
这些代码段展示了如何使用插入排序对链表进行排序，以及如何删除链表中的重复节点。可以根据需要对其进行修改和扩展。