#include <iostream>

using namespace std;

//single link
struct slink_t{
    struct slink_t* next;
    int data;
    slink_t(): next(0), data(0){
    }
    slink_t(slink_t* p, int d): next(p), data(d){
    }
};

/*output data of single link */
ostream& operator<< (ostream& os, const struct slink_t* p)
{
    cout << "Output : ";
    while (p && cout << p->data << ' ')
        p = p->next;
    return os;
}

/* reverse the single link */
struct slink_t* slink_reverse(struct slink_t* p)
{
    struct slink_t* t = NULL, *tp = NULL;
    while (p)
    {
        tp = t;
        t = p;
        p = p->next;
        t->next = tp;
    }
    return t;
}

//double link
struct dlink_t{
    struct dlink_t* next;
    struct dlink_t* prev;
    int data;
    dlink_t(): next(0), prev(0), data(0){
    }
    dlink_t(dlink_t* n, dlink_t* p, int d): next(n), prev(p), data(d){
    }
};

/* output data of double link */
ostream& operator<< (ostream& os, const struct dlink_t* p)
{
    cout << "Output : ";
    while (p && cout << p->data << ' ')
        p = p->next;
    return os;
}

/* reverse the double link */
struct dlink_t* dlink_reverse(struct dlink_t* p)
{
    struct dlink_t* t = NULL;
    while (p)
    {
        t = p;
        p = p->next;
        t->next = t->prev;
        t->prev = p;
    }
    return t;
}

#define TEST__

#ifdef TEST__
/* test */
int main()
{
    struct slink_t* sl = new slink_t(new slink_t(new slink_t(new slink_t(new slink_t(new slink_t(NULL, 6), 5), 4), 3), 2), 1);
    cout << sl << endl;
    sl = slink_reverse(sl);
    cout << sl << endl;
    struct dlink_t* dl = NULL;
    struct dlink_t* h = new dlink_t(NULL, dl, 1);
    dl = h;
    for (int i = 2; i < 10; i++)
    {
        struct dlink_t* t = new dlink_t(NULL, dl, i);
        dl->next = t;
        dl = t;
//        dl->prev->next = dl;
    }
    cout << h << endl;
    h = dlink_reverse(h);
    cout << h << endl;
    cout << "Hello world" << endl;
    return 0;
}
#endif