#include <iostream>

using namespace std;

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode(int x =0) : val(x), next(NULL) {}
};

void ReverseList(ListNode ** head, ListNode* tail)
{
   ListNode * p = *head;
   ListNode * q = tail;
   ListNode * n;

   //make 'next' pointer of node point to previous node
   while( p != tail)
   {
      n = p->next;
      p->next = q;
	
      q = p;
      p = n;
    }

   //make head pointer to new start
   *head = q;
}

ListNode *SwapPairs(ListNode *head) 
{
    ListNode ** h = &head;
    ListNode * t = head;
    ListNode * n = head;
	
    while(1)
    {
        int count = 2;
        while(--count > 0 && t != NULL)
        {
            t = t->next;
        }

        if (t == NULL) break;
		
		//after reverse the list, the head node would be the last node,
		//and pointer to the next segment, we need to reserve this node 
		//to find next start point
		n = *h;
		
		ReverseList(h, t->next);
		
		//begin next reverse
        h = &n->next;
        t= n->next;
    }

    return head;    
}


void PrintList(ListNode* head)
{
	while (head!=NULL)
	{
		cout << head->val<< ", ";
		head = head ->next;
	}
	cout << endl;
}

int main(int argc, char** argv)
{
    const int size = 4;
    ListNode nodes[size];
    for (int i = 0; i < size; ++i)
    {
        nodes[i] = i;
        nodes[i].next = (i ==(size -1)? NULL :&nodes[i+1]);
    }
	
   ListNode* head =  SwapPairs(nodes);
	PrintList(head);
    return 0;
}