C++ 单向链表反转

浏览数：67 / 时间：2015年06月08日

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

 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 \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 }