围绕给定值对链表进行分区，如果我们不关心使列表元素“稳定”

引言

链表是计算机科学中的基本数据结构，因为它们提供了有效的插入和删除操作以及动态内存分配。编程面试和实际应用中的一个常见障碍是围绕特定值分割链表。要完成此挑战，应改进列表的项，以便值为小于给定值的节点出现在值为等于或大于该值的节点之前。当不需要维护原始元素顺序（稳定性）时，分区可以变得更简单。

示例

考虑一个包含任意数量元素的链表

1 -> 7 -> 3 -> 6 -> 5 -> 2 -> 8 -> 4

让我们想象一下，我们围绕一个特定的数字对其进行分割。分割后，列表应如下所示

1 -> 3 -> 2 -> 4 -> 7 -> 6 -> 5 -> 8

然而，每个分区内元素的相对位置可能会有所不同。

不考虑稳定性的方法

在不考虑稳定性的情况下，我们可以使用一种简单的方法来分割链表。在遍历列表的过程中，我们会考虑两个分区：一个用于小于指定值的元素，另一个用于大于或等于指定值的元素。在遍历期间，我们将根据其值将节点从原始列表移动到相应分区。

代码

输出

代码解释

结构定义

• 链表中的每个节点都由一个 ListNode 结构表示。
• 每个节点包含一个指向其后继节点（next）的指针和一个整数值（val）。

分区函数

• partition 函数使用整数 x 和指向链表头部的指针作为输入。
• 初始化两个虚拟节点 before_head 和 after_head，并分别指向它们 before 和 after 的引用。
• 然后，遍历链表。
• 如果当前节点的值小于 x，则将其附加到前一个分区。否则，将其添加到后面的分区。
• 处理完所有节点后，它会将 before 和 after 分区连接在一起，并将 after 分区连接到 NULL。
• 最终，它返回分区后链表的头部。

打印列表函数

• printList 函数在接收到链表的头部作为输入后，打印链表的元素。
• 它在遍历列表直到到达末尾 (NULL) 时打印每个节点的值。

主函数

• main 函数中构建了一个具有值 1 -> 4 -> 3 -> 2 -> 5 -> 2 的示例链表。
• 使用 malloc 动态地为每个节点分配内存。
• 使用 printList 函数打印原始列表。
• X 是一个整数，值为 3。
• 调用 partition 函数来围绕 x 分割列表。
• 使用 printList 函数打印由此产生的分区后列表。

结论

当稳定性不是问题时，围绕给定值对链表进行分区是一个基本的计算机科学问题。通过实现一种遍历列表并将元素根据其值进行分割的简单方法，我们可以有效地完成所需的分割。此方法为手头的问题提供了一个可行的解决方案，适用于各种软件开发应用程序以及其他领域。