C++程序：将链表中的重复节点替换为副本

1. 简介

在计算机编程中，链表是常见的数据结构之一，但有时会出现链表中存在相同的节点，需要将其替换为副本，这篇文章将介绍如何在C++中实现这个功能。

2. 需求分析

对于一个给定的单链表，需要遍历链表中的每一个节点，若节点中的数据与其后的节点中的数据相同，则将后续出现的节点替换为该节点的副本。

2.1 链表节点的定义

链表节点一般分为两个部分，一个是存储数据的成员变量，另一个是指向下一个节点的指针。

struct ListNode {

    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

上述代码中，定义了一个名为ListNode的结构体，其中包含一个整型成员变量val，和一个指向下一个节点的指针next。该结构体的构造函数负责初始化节点中的成员变量。

3. 解决方案

3.1 遍历链表

首先要遍历链表中的每一个节点，可以用一个while循环来实现。

ListNode* temp = head; // head指向链表头部

while(temp != NULL) {
    // 处理节点
    temp = temp->next;
}

上述代码中，temp指向头节点，循环遍历整个链表，直到temp指向NULL，即到达链表结尾。

3.2 判断相同节点

在遍历链表的过程中，需要判断当前节点是否与后续的节点相同。可以设置两个指针，一个指向当前节点，另一个指向当前节点的下一个节点，比较它们的值是否相同。

ListNode* temp = head;

while(temp != NULL && temp->next != NULL) {
    if(temp->val == temp->next->val) {
        // 处理重复节点
    }
    temp = temp->next;
}

上述代码中，第一个if语句判断当前节点和后续节点的值是否相同，若相同，则需要继续处理重复节点，否则继续遍历下一个节点。

3.3 替换重复节点

由于重复节点需要替换为该节点的副本，故需要定义一个函数来实现节点的复制，然后在遍历链表的过程中，将后续出现的重复节点替换为该节点的副本。

ListNode* copyNode(ListNode* node) { // 复制链表节点

    ListNode* copy = new ListNode(node->val);
    return copy;
}
ListNode* temp = head;
while(temp != NULL && temp->next != NULL) {
    if(temp->val == temp->next->val) {
        ListNode* copy = copyNode(temp);
        copy->next = temp->next->next;
        temp->next = copy;
    }
    temp = temp->next;
}

上述代码中，首先调用copyNode函数复制重复节点，然后将复制的节点插入到当前节点和后续节点之间，最后继续遍历下一个节点。

4. 实例演示

下面是完整的实现代码示例：

struct ListNode {

    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
ListNode* copyNode(ListNode* node) {  // 复制链表节点
    ListNode* copy = new ListNode(node->val);
    return copy;
}
void deleteList(ListNode* head) {  // 删除链表
    while(head != NULL) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
}
void printList(ListNode* head) {  // 打印链表
    while(head != NULL) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}
void replaceDuplicateNodes(ListNode* head) {  // 替换重复节点
    ListNode* temp = head;
    while(temp != NULL && temp->next != NULL) {
        if(temp->val == temp->next->val) {
            ListNode* copy = copyNode(temp);
            copy->next = temp->next->next;
            temp->next = copy;
        }
        temp = temp->next;
    }
}
int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(4);
    head->next->next->next->next->next = new ListNode(4);
    head->next->next->next->next->next->next = new ListNode(5);
    cout << "Original list: ";
    printList(head);
    replaceDuplicateNodes(head);
    cout << "List after duplicates replaced: ";
    printList(head);
    deleteList(head);
    return 0;
}

5. 总结

本文介绍了如何使用C++将链表中的重复节点替换为副本。需要注意的是，对于链表这种数据结构，需要注意指针的使用和创建和删除节点的方法，才能有效地操作链表。