C++ 单链表的交替分割

在本文中，我们将讨论如何在 C++ 中对给定的**单链表**进行交错**分割**，并附上解释和好处。

我们以一个单链表作为输入。在这里，我们的主要目标是将该列表分成两个单链表，这两个链表包含原始列表中的不同节点。如果输入列表包含节点 a、b、c、d、e 和 f，那么分割后的两个子列表将是 a、c、e 和 b、d、f。

之后，我们将选取两个指针 **N1** 和 **N2**，一个指向原始列表的头部，另一个也指向同一个头部。将两个指针移动到后续节点以构建子列表。

示例

输入 - 列表：- 1 → 5 → 7 → 12 → 2 → 96 → 33

输出 - 原始列表: 1 5 7 12 2 96 33

列表 1: 1 7 2 33

列表 2: 5 12 96

解释 - 从 1 和 5 开始，next 指针指向交替的节点，以创建如上所示的子列表。

输入 - 列表：- 13 → 53 → 90 → 18 → 44 → 11→ 99 → 32

输出 - 原始列表 13 53 90 18 44 11 99 32

列表 1: 13 90 44 99

列表 2: 53 18 11 32

解释 - 从 13 和 53 开始，next 指针指向交替的节点，以创建如上所示的子列表。

简单方法

在这个方法中，我们将使用两个指针 **N1** 和 **N2**，一个指向原始列表的头部，另一个指向下一个列表的头部。将两个指针移动到后续节点以构建子列表。

1. 考虑一个包含一个 int 数据部分和一个作为 next 指针的节点的结构。
2. 使用函数 addtohead(Node** head, int data) 将节点添加到头部来构建一个单链表。
3. 使用前面提到的代码创建一个单链表，并使用一个指向第一个节点的指针作为头部。
4. 使用函数 display(Node* head) 从头节点开始打印链表。
5. 考虑 Node1 和 Node2 指针。
6. 节点指针在 splitList 函数中使用，该函数将 Node* head, Node** n1 和 Node** n2 指向原始字符串的头部和下一个节点。
7. 在其中使用 split(*n1, *n2) 将原始列表分成两个子列表。
8. split(Node* N1, Node* N2) 函数接受两个指针 N1 和 N2，并生成两个子列表，每个子列表包含原始列表中的交替节点。
9. 如果 N1 和 N2 都为空，则不返回任何内容。
10. 如果 N1 的 next 不为空，则设置 tmp=N1->next->next 并将 N1->next 设置为 tmp；如果 N2 的 next 不为空，则设置 tmp=N2->next->next 并将 N2->next 设置为 tmp；然后调用 split(N1->next, N2->next) 进行下一次迭代。
11. 最后使用 display() 函数打印子列表。

程序

让我们举个例子来说明如何在 C++ 中对给定的**单链表**进行交错**分割**。

输出

交错分割给定单链表的好处

将一个**单链表**交错分割成两个部分，通常是通过将其分成两个不同的列表，一个包含偶数位置的节点，另一个包含奇数位置的节点。我们可以通过遍历原始列表几次并为奇数和偶数位置创建两个独立的列表来实现这一点。在 C++ 中交错分割单链表的好处包括以下几点：

1. 更好的数据组织： 通过将列表分成两个**子列表**，我们可以更逻辑地组织数据。当处理具有特定模式的项目或需要分别对奇数和偶数元素执行操作时，这会非常有帮助。
2. 简化数据处理： 交错分割可以简化某些数据处理操作。例如，通过隔离项目的交替属性（例如，学生有学号和姓名），分割列表可以使处理变得更容易。
3. 并行性： 在某些情况下，可能需要并行处理列表的奇数和偶数项。在多核计算机中，将列表分成奇数和偶数部分可以通过促进并行处理来提高性能。
4. 算法练习： 将链表交错分割成几个部分是练习操作和遍历链表的好方法。这将提高处理链接数据结构的能力。
5. 模块化代码： 创建函数或方法来执行交错分割，可以增加我们代码的模块化和可维护性。这种关注点分离可以提高代码的可读性和可重用性。
6. 增强测试： 将列表分成两部分使得在每个部分上测试和排查特定活动变得更容易。我们可以专注于测试偶数位置节点的逻辑，而与奇数位置节点的逻辑分开。
7. 灵活性： 将单链表交错分割的能力为数据处理和操作提供了灵活性。我们可以修改代码以适应不同的数据模式和规范。