令 L 为长度为 m 的双向链表，存储在数组 key、prev 和 next 中，它们的长度均为 n。假设这些数组由 ALLOCATE_OBJECT 和 FREE_OBJECT 过程管理，它们保持一个双向链接的空闲列表 F。进一步假设 n 个项目 [可以由三个数组描述，恰好 m 在列表 L 上，而其他 nm 在自由列表 F. 编写一个程序 COMPACTIFY_LIST(L,F) 移动 L 中的项目，使它们占据数组位置 1,2,...,m 并调整所有数组中的索引值，以便 L 列出保持相同的顺序，并且 F 列表包含与以前相同数量的元素，现在占据数组中的位置 m+1、m+1、..、n。
我只能想到一个保留两个指针的 O(n) 程序。我从数组键开头的两个指针开始。Pointer1 查找第一个可用的空白空间，然后 pointer2 查找该位置之后的数组的第一个索引，该索引包含链表的一个元素。然后将这个元素移动到pointer1所指向的位置，然后pointer1寻找下一个空白处继续。但是如果我没记错的话，这个过程将花费 O(n) 时间。我想不出一个 O(m) 算法。
PS 是的，这是作业。但我被困住了，我们将不胜感激。