Implementing the Dutch National Flag Program with Linked Lists

Question

I wanted to sort a linked list containing 0s, 1s or 2s. Now, this is clearly a variant of the Dutch National Flag Problem. http://en.wikipedia.org/wiki/Dutch_national_flag_problem

The algorithm for the same as given in the link is:

"Have the top group grow down from the top of the array, the bottom group grow up from the bottom, and keep the middle group just above the bottom. The algorithm stores the locations just below the top group, just above the bottom, and just above the middle in three indexes. At each step, examine the element just above the middle. If it belongs to the top group, swap it with the element just below the top. If it belongs in the bottom, swap it with the element just above the bottom. If it is in the middle, leave it. Update the appropriate index. Complexity is Θ(n) moves and examinations."

And a C++ implementation given for the same is:

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;
    }
  }

}

My only question is how do we traverse back in a linked list like we are doing here in an array?

Answer 1

A standard singly-linked list doesn't allow you to move backwards given a linked list cell. However, you could use a doubly-linked list, where each cell stores a next and a previous pointer. That would let you navigate the list forwards and backwards.

However, for the particular problem you're trying to solve, I don't think this is necessary. One major difference between algorithms on arrays and on linked lists is that when working with linked lists, you can rearrange the cells in the list to reorder the elements in the list. Consequently, the algorithm you've detailed above - which works by changing the contents of the array - might not actually be the most elegant algorithm on linked lists.

If you are indeed working with linked lists, one possible way to solve this problem would be the following:

• Create lists holding all values that are 0, 1, or 2.
• Remove all cells from the linked list and distribute them into the list of elements that are equal to 0, 1, or 2.
• Concatenate these three lists together.

This does no memory allocation and purely works by rearranging the linked list cells. It still runs in time Θ(n), which is another plus. Additionally, you can do this without ever having to walk backwards (i.e. this works on a singly-linked list).

I'll leave the complete implementation to you, but as an example, here's simple C++ code to distribute the linked list cells into the zero, one, and two lists:

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;
}

Hope this helps!