单向链表反转，一道常见的面试题，动手实现下。

1 #include "stdafx.h" 2 #include 
     
       3 struct Node{ 4     int data; 5     Node* next; 6 }; 7  8 void print1(Node *head)   9 {  10     Node *p;  11     p=head;  12     if(head!= NULL)  13     do  14     {  15     printf("%d \n", p->data);  16     p=p->next;  17     }while(p!=NULL);  18 }19 20 Node* ReverseList(Node* head)21 {22     if(head==NULL)23         return NULL;24 25     Node* cur=head;26     Node* pre=NULL;27     Node* nx=NULL;28     while(cur->next!=NULL)29     {30         nx=cur->next;31         cur->next=pre;32         pre=cur;33         cur=nx;34     }35     cur->next=pre;36     return cur;37 }38 Node* init( int num) // insert from back  39 {  40     if(0 >= num)  41         return NULL;  42     Node* cur, pre;  43     Node* head = NULL;  44     int i = 0; cur = head;  45     Node* new1 = (Node*)malloc(sizeof(Node));  46     new1->data = 1;  47     head = cur = new1;  48     for(i = 1; i < num; i++)  49     {  50         Node* new1=(Node*)malloc(sizeof(Node));  51         new1->data = i + 1;  52         cur->next = new1;  53         cur = new1;  54     }  55      cur->next = NULL;     56     return head;      57 }  58 int _tmain(int argc, _TCHAR* argv[])59 {60     Node* list =NULL;61     list=init(10);62     print1(list);63     Node* newlist=ReverseList(list);64     print1(newlist);65     getchar();66     return 0;67 }
     

原理就是把cur节点的next节点保存，把next指向pre节点，把之前保存的next节点赋给cur，不断循环直到next节点为NULL。注意下，退出循环后要把cur节点next指向pre节点。把cur节点返回，大功告成。

如果不用返回值，而是把head=cur；这样可以吗？

可尝试下，那么你会看到打印结果为1。这是因为函数按指针传递，传递的是地址，虽然在reverse函数中head已是一个反转的链表，但在main函数中list仍然指向原来head的地址。换句话说，在反转链表整个过程中地址是不变的，list还是指向data 1的节点。