#include <iostream>

using namespace std;

struct node 
{
    int data;
    struct node *next;
};

void insert_list(node **head, int i)
{
    node *p = *head;
    node *pre = p;
    while (p != NULL) {
        pre = p;
        p = p->next;
    }

    node* node_inst = new node();
    node_inst->data =http://www.mamicode.com/ i;
    node_inst->next = NULL;
    if (*head == NULL) {
        *head = node_inst;
    } else {
        pre->next = node_inst;
    }
}

void list_revert(node **head) 
{
    if (*head == NULL) return;

    node *pre = NULL;
    node *cur = *head;
    node *next = (*head)->next;

    while (next != NULL) {
        cur->next = pre;
        pre = cur;
        cur = next;
        next = next->next;
    }
    cur->next = pre;
    *head = cur;
}

node * list_merge(node *head1, node *head2)
{
    if (head1 == NULL) return head2;
    if (head2 == NULL) return head1;
    
    node *new_head = NULL;
    if (head1->data < head2->data) {
        new_head = head1;
        new_head->next = list_merge(head1->next, head2);
    } else {
        new_head = head2;
        new_head->next = list_merge(head1, head2->next);
    }

    return new_head;
}

int main()
{
    node *head1 = NULL;

    for (int i = 0; i < 10; i += 2) {
        insert_list(&head1, i);
    }

    node *p = head1;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

    //list_revert(&head1);
    //p = head1;
    //while (p != NULL) {
    //    cout << p->data << " ";
    //    p = p->next;
    //}
    //cout << endl;

    node *head2 = NULL;

    for (int i = 1; i < 10; i += 2) {
        insert_list(&head2, i);
    }
    p = head2;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

    p = list_merge(head1, head2);
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;

    getchar();

    return 0;
}