C++程序删除链表的交替节点

在我们的日常工作中，经常需要进行一些针对链表的操作，如删除节点、添加节点等。本文将介绍如何使用C++语言编写一个函数，来实现删除一个链表的交替节点的功能。

链表的基本概念

在开始编写代码之前，我们需要先了解链表的一些基本概念。

链表是一种常用的数据结构，它由若干个节点(node)组成，每个节点包含两个部分：数据域和指针域。数据域存储节点所需的数据，指针域指向下一节点的地址。

链表由头节点和尾节点组成，头节点是链表的第一个节点，尾节点是链表的最后一个节点，每个节点的指针域指向下一个节点，最后一个节点指向NULL。下面是一个简单的链表结构示例：

struct ListNode {
    int val; // 数据域
    ListNode *next; // 指针域
    ListNode(int x) : val(x), next(NULL) {} // 构造函数
};

在这个结构中，val表示节点中存储的数据，next是指向下一个节点的指针。

链表的交替节点

链表的交替节点即删除链表中奇数位置的节点或偶数位置的节点。例如，对于以下链表：

1 -> 2 -> 3 -> 4 -> 5 -> NULL

删除奇数位置的节点后，得到的链表是：

2 -> 4 -> NULL

删除偶数位置的节点后，得到的链表是：

1 -> 3 -> 5 -> NULL

C++程序实现

接下来，我们将展示如何使用C++编写一个简单的函数，来实现删除链表的交替节点的功能。

ListNode* deleteAlternateNodes(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;
    int count = 1;

    while(cur != nullptr) {
        if(count % 2 == 0) {
            prev->next = cur->next;
            delete cur;
            cur = prev->next;
        } else {
            prev = cur;
            cur = cur->next;
        }

        count++;
    }

    return head;
}

在这个函数中，head表示传递给函数的链表的头节点。首先，我们定义两个指针prev和cur，分别指向当前节点的前一个节点和当前节点。我们使用count计数，来判断当前节点是否为交替节点，如果是，则将其删除；否则，继续遍历链表。

具体的实现逻辑如下：

如果count是偶数，则删除当前节点，即将prev的next指向cur的下一个节点，再删除cur。
如果count是奇数，则将prev指向cur，然后将cur指向下一个节点。

最后，函数返回链表的头节点head。

完整代码

下面是完整的C++代码，包括链表的定义和删除交替节点的函数实现：

#include <iostream>

using namespace std;

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

ListNode* deleteAlternateNodes(ListNode* head) {
    ListNode* prev = nullptr;
    ListNode* cur = head;
    int count = 1;

    while(cur != nullptr) {
        if(count % 2 == 0) {
            prev->next = cur->next;
            delete cur;
            cur = prev->next;
        } else {
            prev = cur;
            cur = cur->next;
        }

        count++;
    }

    return head;
}

void printList(ListNode* head) {
    ListNode* cur = head;

    while(cur != nullptr) {
        cout << cur->val << " -> ";
        cur =cur->next;
    }

    cout << "NULL" << endl;
}

int main() {
    // 创建链表
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);

    // 打印原始链表
    cout << "Original list: ";
    printList(head);

    // 删除偶数位置节点
    head = deleteAlternateNodes(head);

    // 打印删除后的链表
    cout << "After deleting alternate nodes: ";
    printList(head);

    return 0;
}

首先，我们创建一个含有5个元素的链表，然后使用printList函数打印原始链表。接着，我们调用deleteAlternateNodes函数，删除链表的交替节点。最后，再次调用printList函数，打印删除后的链表。