逆转单向链表

1. 逆转单向链表

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

//定义链表的节点。
struct Link {
    Link* next;
    int value;
};

//递归方式：逆转单向链表
Link* reverse1(Link *head)
{
    if(head == NULL ) return NULL;
    if(head->next == NULL) return head;

    Link* tail = NULL;
    Link* temp = head->next;
    tail = reverse1(head->next);
    temp->next = head;
    head->next = NULL;
    return tail;
}
//非递归方式：逆转单向链表
void reverse(Link **head)
{
    if(!head || !(*head)) return;
    Link *pre, *cur, *nex;
    pre = NULL, cur=*head;
    while(cur) {
        nex = cur -> next;
        cur->next = pre;
        pre = cur;
        cur = nex;
    }
    *head = pre;
}

//输出整个链表
void printLink(Link *head)
{
    Link *curr = head;
    while(curr) {
        printf("%d ", curr->value);
        curr = curr->next;
    }
    printf("\n");
}

int main(void)
{
    Link *head, *p[10], *newhead;
    int num = 10;
    for(int i=0; i<num; i++) {
        p[i] = new Link();
        p[i]->next = NULL;
        p[i]->value = i+1;
        if (i==0) head = p[i];
        else p[i-1]->next = p[i];
    }
    printLink(head);
    reverse(&head);
    printLink(head);
    for(int i=0; i<num; i++) delete p[i];
    system("pause");
}