C++ 程序将单向链表按奇偶节点交替顺序排列

引言

链表是计算机科学中基本的数据结构，它提供了一种有效组织和操作数据的方法。链表领域中一个有趣的问题是以奇偶交替顺序排列节点。此任务涉及重新排序节点，使得所有奇数位置的节点首先出现，然后是偶数位置的节点。

理解问题

考虑一个节点编号为 1、2、3、4 等的链表。我们的目标是重新排列节点，使所有奇数位置的节点首先出现，然后是偶数位置的节点。例如，给定链表

所需的排列是

算法概述

该算法涉及遍历链表，识别奇数和偶数节点，并重新排列它们以创建具有奇偶交替节点的新链表。让我们分解这些步骤：

• 创建一个具有随机值的链表以进行演示。
• 遍历原始链表，将节点分成奇数组和偶数组。
• 为奇数节点和偶数节点创建两个单独的链表。
• 交替连接奇数链表和偶数链表，形成最终的排列链表。
• 显示原始链表和排列后的链表以进行比较。

方法 1：分离奇数和偶数节点，然后合并

第一种方法是将奇数和偶数节点分离成两个单独的链表，然后交替合并它们。以下是此方法的 C++ 代码：

说明

• 此 C++ 程序定义了一个单链表结构（Node），并提供了一个函数（arrangeList）来重新排列链表元素，使得所有奇数位置（基于 1）的节点都放置在偶数位置的节点之前。
• arrangeList 函数将链表头部的引用作为参数，并就地修改链表。
• arrangeList 函数首先检查链表是否为空或只有一个元素，在这种情况下不需要重新排列。
• 如果链表中有多个元素，该函数初始化四个指针（oddHead、evenHead、oddTail 和 evenTail）以管理两个独立的链表——一个用于奇数位置的节点，另一个用于偶数位置的节点。
• 然后，该函数遍历原始链表，根据节点位置进行划分。
• 奇数位置的节点链接在一起形成一个新链表（oddHead 到 oddTail），同样，偶数位置的节点形成另一个链表（evenHead 到 evenTail）。
• 遍历原始链表后，该函数将奇数链表和偶数链表的尾节点的下一个指针都设置为 nullptr 以终止它们。
• 最后，该函数通过将奇数链表尾节点的下一个指针设置为偶数链表的头部来合并这两个链表。修改后的链表的头部更新为指向奇数链表的头部。
• 提供了 printList 函数来打印链表的元素。在 main 函数中，创建一个示例链表，打印，然后使用 arrangeList 函数重新排列，并再次打印修改后的链表以演示程序的功能。

程序输出

方法 2：就地重新排列

此方法涉及就地重新排列节点，而无需使用额外的数据结构。以下是此方法的 C++ 代码：

说明

• 此 C++ 程序定义了一个单链表结构（Node），并提供了一个函数（arrangeList）来重新排列链表元素，使得所有偶数位置（基于 0）的节点都位于奇数位置的节点之后。
• arrangeList 函数将链表头部的引用作为参数，并就地修改链表。
• arrangeList 函数使用三个指针：odd、even。它将 odd 初始化为链表的头部，将 even 初始化为第二个节点（如果存在）。
• evenStart 指针用于跟踪偶数位置节点的起始点，从而方便稍后与奇数位置节点链接。
• 然后，该函数遍历链表，更新指针以重新排列节点。在每次迭代中，它将 odd 指针移动到下一个奇数位置节点，将 even 指针移动到下一个偶数位置节点。
• odd->next 设置为 even->next，以跳过当前迭代中的偶数位置节点，有效地将奇数位置节点链接在一起。同时，even->next 更新为下一个偶数位置节点。
• 循环继续，直到 even 变为 nullptr 或 even->next 变为 nullptr，表示链表结束。循环结束后，该函数将最后一个奇数位置节点链接到偶数位置节点的起始点（evenStart）。
• 提供了 printList 函数来打印链表的元素。在 main 函数中，创建一个示例链表，打印，然后使用 arrangeList 函数重新排列，并再次打印修改后的链表以演示程序的功能。

程序输出

时间复杂度

该方法的时间复杂度为 O(N)，其中 N 是链表中的节点数。这是因为算法遍历链表中的每个节点一次，并且循环中执行的操作是常数时间。

空间复杂度

该方法的空间复杂度为 O(1)。它使用恒定量的额外空间用于临时指针（oddHead、evenHead、oddTail、evenTail），而与链表的大小无关。

结论

总之，C++ 程序以奇偶交替顺序排列单链表节点，为重新组织链表元素提供了一个实用且高效的解决方案。

通过分离奇数和偶数节点，然后以交替方式重新排列它们，该程序增强了链表的结构和可读性。所采用的算法展示了一种系统方法，遍历链表并适当地调整指针以实现所需的顺序。

此外，该程序展示了 C++ 在实现复杂数据结构和算法方面的多功能性，利用了该语言的指针和动态内存分配等特性。代码的模块化设计促进了代码重用性和可维护性，这在软件开发中是必不可少的品质。

然而，需要注意的是，程序的有效性取决于链表的初始结构和内容。必须仔细考虑边缘情况并进行彻底测试，以确保程序在各种场景中的健壮性和可靠性。总的来说，用于以奇偶交替顺序排列单链表的 C++ 程序为使用链式数据结构的开发人员提供了宝贵的工具，展示了 C++ 在算法实现中的强大功能和灵活性。