title: Implementing the Dutch National Flag Program with Linked Lists
body: <p>I wanted to sort a linked list containing 0s, 1s or 2s. Now, this is clearly a variant of the Dutch National Flag Problem.
  <a href="http://en.wikipedia.org/wiki/Dutch_national_flag_problem" rel="nofollow">http://en.wikipedia.org/wiki/Dutch_national_flag_problem</a></p>
  
  <p>The algorithm for the same as given in the link is: </p>
  
  <p>"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."</p>
  
  <p>And a C++ implementation given for the same is:</p>
  
  <pre><code>void threeWayPartition(int data[], int size, int low, int high) {
    int p = -1;
    int q = size;
    for (int i = 0; i &lt; q;) {
      if (data[i] == low) {
        swap(data[i], data[++p]);
        ++i;
      } else if (data[i] &gt;= high) {
        swap(data[i], data[--q]);
      } else {
        ++i;
      }
    }
  </code></pre>
  
  <p>}</p>
  
  <p>My only question is how do we traverse back in a linked list like we are doing here in an array?</p>