C++ 单向链表反转

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

 1 #include "stdafx.h"
 2 #include <stdlib.h>
 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 
", 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的节点。