C++：链表插入排序/删除重复节点

在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 node
            next = curr->next;
            curr->next = next->next;
            prev = dummy;

            // Locate the insertion point
            while (prev->next && prev->next->val < next->val) {
                prev = prev->next;
            }

            // Insert the node
            next->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 nullptr
    ListNode* 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 -> nullptr
    ListNode* 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 sort
    head = insertionSortList(head);
    std::cout << "Sorted list:" << std::endl;
    printList(head);

    // Delete duplicates, keeping only unique elements
    head = deleteDuplicatesAll(head);
    std::cout << "List after deleting all duplicates:" << std::endl;
    printList(head);

    // Create another sample linked list: 1 -> 1 -> 2 -> 3 -> 3 -> nullptr
    head = 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 instance
    head = deleteDuplicates(head);
    std::cout << "List after deleting duplicates (keeping one):" << std::endl;
    printList(head);

    return 0;
}