【算法】链表翻转

0x55AA

1. #include <iostream>
   
2. using namespace std;
   
3. 
   
4. struct Node
   
5. {
   
6.         int key;
   
7.         Node* next;
   
8. };
   
9. Node* createList(int arr[],int nLength);
   
10. Node* reverseList(Node* head);
    
11. void printList(Node* head);
    
12. void clearList(Node* head);
    
13. 
    
14. void main()
    
15. {
    
16.         int arr[] = {1,3,5,7,9};
    
17.         int nLength = sizeof(arr)/sizeof(arr[0]);
    
18.         Node* head = createList(arr,nLength);
    
19.         printList(head);
    
20.         head = reverseList(head);
    
21.         printList(head);
    
22.         clearList(head);
    
23. }
    
24. 
    
25. Node* createList(int arr[],int nLength)
    
26. {
    
27.         Node* head = new Node;
    
28.         head->key = arr[0];
    
29.         head->next = NULL;
    
30.         Node *p = head;
    
31.         for(int i=1;i<nLength;i++)
    
32.         {
    
33.                 Node* ptr = new Node;
    
34.                 ptr->key = arr[i];
    
35.                 ptr->next = NULL;
    
36.                 p->next = ptr;
    
37.                 p = p->next;
    
38.         }
    
39.         return head;
    
40. }
    
41. 
    
42. Node* reverseList(Node* head)
    
43. {
    
44.         Node* preNode = NULL;
    
45.         Node* pNode = head;
    
46.         while( pNode != NULL )
    
47.         {
    
48.                 Node* pNext = pNode->next;
    
49.                 pNode->next = preNode;
    
50.                 preNode = pNode;
    
51.                 pNode = pNext;
    
52. 
    
53.         }
    
54.         return preNode;
    
55. }
    
56. 
    
57. void printList(Node* head)
    
58. {
    
59.         Node* p = head;
    
60.         while( p!= NULL )
    
61.         {
    
62.                 cout<<p->key<<endl;
    
63.                 p=p->next;
    
64.         }
    
65. }
    
66. 
    
67. void clearList(Node* head)
    
68. {
    
69.         Node* p = head;
    
70.         Node* ptr;
    
71.         while( p!= NULL )
    
72.         {
    
73.                 ptr = p->next;
    
74.                 delete p;
    
75.                 p = ptr;
    
76.         }
    
77. }

复制代码