//
// All exchanges are done to pointers
//

#include <iostream>

class Node {
public:
  int data;
  Node* next, *prev;
  Node (int a, Node* p, Node* n) { next = n; prev = p; data = a; }
};

void
Swap (Node*& A, Node*& B)
{
  if (A == B) return;

  Node* Tmp;
  if (A->next && (A->next != B)) A->next->prev = B;
  if (B->next && (B->next != A)) B->next->prev = A;
  if (A->prev && (A->prev != B)) A->prev->next = B;
  if (B->prev && (B->prev != A)) B->prev->next = A;

  Tmp = A->next; 
  if (B->next != A) A->next = B->next; else A->next = B;
  if (Tmp != B) B->next = Tmp; else B->next = A;

  Tmp = A->prev;
  if (B->prev != A) A->prev = B->prev; else A->prev = B;
  if (Tmp != B) B->prev = Tmp; else B->prev = A;

  Tmp = A; A = B; B = Tmp;
}

bool
Partition (Node*& Front, Node*& Rear, Node*& Pivot)
{
  int fr = 0, fl = 0;
  int direction = 0;
  Node *L = Front, *R = Rear;

  while (L != R)
    {
      if (L->data > R->data)
        {
          direction = 1 - direction;
          Swap (L, R); 
        }
      if (direction) {
        if (fr == 0) Rear = R; 
        fr = 1; R = R->prev;
      } else {
        if (fl == 0) Front = L;
        fl = 1; L = L->next;
      }
    }
  Pivot = L;
}

bool 
PrintNodes (Node* Front)
{
  for (; Front != NULL; Front = Front->next)
    cout << Front->data << " ";
  cout << endl;
}

int
main (int argn, char *argv[])
{
  Node *Front = new Node (6, NULL, NULL);
  Node *N1 = new Node (1, Front, NULL);
  Node *N2 = new Node (3, N1, NULL);
  Node *N3 = new Node (5, N2, NULL);
  Node *Rear = new Node (4, N3, NULL);

  Node *Pivot = NULL;

  Front->next = N1;
  N1->next = N2;
  N2->next = N3;
  N3->next = Rear;

  PrintNodes (Front);
  Partition (Front, Rear, Pivot);
  PrintNodes (Front);
  cout << "Pivot: " << Pivot->data << endl;

  return 0;
}