algorithm - 使用链表实现荷兰国旗程序

Question

我想对包含 0、1 或 2 的链表进行排序。现在，这显然是荷兰国旗问题的一个变体。 http://en.wikipedia.org/wiki/Dutch_national_flag_problem

链接中给出的相同算法是:

“让顶部组从数组顶部向下生长，底部组从底部向上生长，并使中间组保持在底部上方。算法存储顶部组正下方的位置，恰好在顶部组上方的位置bottom, and just above the middle in three indexes. 在每一步中，检查中间以上的元素。如果它属于顶部组，则将其与顶部以下的元素交换。如果它属于底部，则将其交换元素刚好在底部上方。如果它在中间，则保留它。更新适当的索引。复杂度是 Θ(n) 次移动和检查。”

同样的 C++ 实现是:

void threeWayPartition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] == low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }

我唯一的问题是我们如何像在数组中那样遍历链表？

Answer 1

标准的单链表不允许您向后移动给定的链表单元格。但是，您可以使用双向链表，其中每个单元格存储一个下一个和一个上一个指针。这样您就可以向前和向后浏览列表。

但是，对于您要解决的特定问题，我认为没有必要这样做。数组和链表算法之间的一个主要区别是，在使用链表时，您可以重新排列列表中的单元格以重新排列列表中的元素。因此，您在上面详述的算法 - 通过更改数组的内容来工作 - 实际上可能不是链表上最优雅的算法。

如果您确实在使用链表，解决此问题的一种可能方法如下:

• 创建包含所有 0、1 或 2 值的列表。
• 从链表中移除所有单元格，并将它们分配到等于 0、1 或 2 的元素列表中。
• 将这三个列表连接在一起。

这不会分配内存，并且纯粹通过重新排列链表单元格来工作。它仍然在时间 Θ(n) 中运行，这是另一个优点。此外，您无需向后走就可以执行此操作(即这适用于单链表)。

我会将完整的实现留给您，但作为示例，这里有一个简单的 C++ 代码，用于将链表单元分配到零、一和二列表中:

struct Cell {
    int value;
    Cell* next;
}

/* Pointers to the heads of the three lists. */
Cell* lists[3] = { NULL, NULL, NULL };

/* Distribute the cells across the lists. */
while (list != NULL) {
    /* Cache a pointer to the next cell in the list, since we will be
     * rewiring this linked list.
     */
    Cell* next = list->next;

    /* Prepend this cell to the list it belongs to. */
    list->next = lists[list->value];
    lists[list->value] = list;

    /* Advance to the next cell in the list. */
    list = next;
}

希望这对您有所帮助!