学步园

将一个单向链表反转，也就是将1->2->3->4->...->n-1->n这样的链表反转变为n->n-1->...3->2->1，可以这样做，顺序删除链表中的节点，使链表的next指针指向前一个元素，切断与后面元素的联系。这样算法的复杂度是O(N)，只需要N次遍历就可以将链表反转，代码如下：

#include <stdio.h>
#include <stdlib.h>
typedef struct Node* LinkList;

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



void list(int arr[],LinkList l,int n){
        int i;
        LinkList p = l, s;
        for(i = 0; i < n; i++){
                s = (LinkList)malloc(sizeof(Node));
                s->data = arr[i];
                p->next = s;
                p = s;
        }
        p->next = NULL;
}


void traverse(LinkList l){
        LinkList p = l->next;
        while(p != NULL){
                printf("%d\t", p->data);
                p = p->next;
        }
        printf("\n");
}
void reverse(LinkList l){
        LinkList p = l->next;
        LinkList s = NULL, q = NULL;
        while(p != NULL){
                s = p->next;
                p->next = q;
                q = p;
                p = s;
        }
        LinkList h = (LinkList)malloc(sizeof(Node));
        h->next = q;
        traverse(h);
}

int main(int argc, char * argv[]){
        int arr[10] = {1,2,3,4,5,6,7,8,9,10};
        LinkList head = (LinkList)malloc(sizeof(Node));
        list(arr, head, 10);
        traverse(head);
        reverse(head);
}