C++ 中将链表中的元素所有出现移到末尾

链表是计算机科学和编程语言中的一种基本数据结构，几乎存在于所有类型的计算机系统中。它与数组不同，通过将通过指针连接的顺序节点组合成一个序列，动态且高效地利用内存。使用链表时的一个典型问题是如何在保持特定顺序或结构的同时更改其元素的位置。

在这篇博客文章中，我们将讨论一个经典的链表问题：将链表中一个元素的所有出现移到列表的末尾。这个问题是处理链表指针、元素顺序和时间复杂度的常见实现。

假设您有一个链表，其中包含多个您的值实例，并且您希望将它们按升序排序，以部分地将它们放在链表的末尾。问题在于，除了目标元素之外的任何元素都必须保持其在初始排列中的相同顺序。此外，如果目标元素重复出现，它们也必须保持其顺序。这使得该问题与之前提到的简单节点重排不同。

为了使这个想法更具体，我举一个例子。假设您有一个链表

该列表以各种元素开头；事实上，列表中有许多个 2。操作结束后，所有的 2 都被移动到列表的倒数第二个元素之前，所有其他元素保持不变，并保持其顺序 1, 3, 4, 5。被移动的 2 也保持其顺序不变。

这个问题在竞争性编程和技术面试中很受欢迎，因为它考验程序员对链表指针工作特点的理解，以及即使乍一看也能快速正确地解决问题的能力。它在现实生活中也很重要，在现实生活中需要对相互关联的数据执行类似操作，并且需要重新排序，例如，对任务进行排序或重新排列动态数据结构的结构组件。

问题陈述

该任务可以正式描述如下

假设您有一个单链表和一个必须放在列表尾部的值 x；以这种方式重新排列列表项。其他元素的位置不应更改，目标值的位置也应保持不变。

例如

为了实现这一点，我们必须仔细处理与链表操作相关的几个关键挑战

指针管理： 链表与数组有些不同，因为没有直接的索引指针；必须通过指针遍历链表才能获取数据元素。由于这些指针是作者提供的唯一移动节点的方式，因此正确控制这些指针非常重要，以免丢失存储的数据或甚至导致列表损坏。

顺序保持： 因此，保持非目标和目标的相对顺序也增加了另一个难度。例如，对于输出，1 -> 3 -> 4 -> 4；对于输入，1 -> 4 -> 4 -> 3。1 和 3 不能互换。同样，4 和 4 也不能互换。

效率： 一个可能的简单解决方案是使用另一个列表或重新遍历原始列表以移动目标元素。然而，这会导致在大型列表上性能不佳；因此可能不适用于大型列表。完美的解决方案应该能够只遍历列表一次，或者在最佳解决方案中，最多两次。

主要挑战

在链表或一般使用指针交换元素，以将给定值的所有出现都放在后面并不容易。这些挑战主要源于链表类型的特点，其中使用节点指针进行节点操作，而不是像数组那样使用索引。

1. 指针管理

链表不支持直接访问元素，因为它只通过指针指向节点。为了移动元素，我们必须更新节点的下一个指针，以使列表保持完整。指针故障会导致链接断裂、循环引用或丢失所需的数据视图。

例如，当节点移动到列表的尾部时，需要首先删除该节点，然后更改前一个节点的指针，并将该节点设为新的尾部。管理此类更改的问题在于，一个级别的任何搅动都可能影响列表的其他方面。

2. 顺序保持

保持非目标节点和目标节点的相对顺序也使事情复杂化。例如，如果输入是 1 -> 2 -> 3 -> 2 -> 4 -> 2，则输出必须包含一个序列，其中非目标节点 (1, 3, 4) 必须与目标节点 (2, 2, 2) 保持相同的顺序。这排除了直接解决问题的方法，例如，通过以其流无关紧要的方式对节点进行分组。

3. 效率

如果算法效率不高，例如，需要对列表进行一次遍历来查找和重新定位目标节点，则时间复杂度为 O(n^2)。对于更长的链表，这种梳理过程在计算上会变得非常昂贵。解决方案的最优性意味着其实现必须在 O(n) 时间内遍历此列表，每个节点只影响一次。

4. 边缘情况

必须解决一些考虑因素，例如当列表为空、列表是单个节点，或者列表等于所有或不等于任何目标值时。这些情况提供了一些额外信息，可用于挑战解决方案并定义其适用性。

编码

输入

输出

 
List after moving all occurrences of the target (2) to the end:
1 -> 3 -> 4 -> 5 -> 2 -> 2 -> 2 -> nullptr