单链表逆置

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
    struct node *next;
    int id;
}node;
node *head;

void traverse(node *p)
{
    while(p)
    {
        printf("%d\n", p->id);
        p = p->next;
    }
}

//insert a node in after the head

void insert(node *p)
{
    node *first = head->next;
    
    head->next = p;
    p->next = first;
}

//inverse the list iteratively

node* inverse1(node *p)
{
    node *p1, *p2, *p3;
    
    //return directly if empty list or only one element in the list

    if((p == NULL) || (p->next == NULL))
        return p;
    
    p1 = p;
    p2 = p1->next;
    while(p2)
    {
        p3 = p2->next;
        p2->next = p1;
        p1 = p2;
        p2 = p3;
    }
    
    p->next = NULL;
    head = p1;
    
    return head;
}

//inverse the list recursively

void inverse2(node *cur, node *pre)
{
    if (!cur)
    {
        head = pre;
        return;
    }
        
    inverse2(cur->next, cur);
    cur->next = pre;
}

int main()
{
    node *p;
    int i;
    
    head = (node *)malloc(sizeof(node));
    head->next = NULL;
    head->id = -1;
        
    for(i = 0; i < 5; i++)
    {
        p = (node *)malloc(sizeof(node));
        p->id = i;
        insert(p);
    }
    
    inverse1(head);
    //inverse2(head, NULL);

    traverse(head);
    
    system("pause");
    return 0;
}