// p 为指向非空单链表中第一个结点的指针，本算法逆转链表并返回逆转后的头指针。基本思路是：如果链表中只有一 个结点，则空操作，否则先逆转a2开始的链表，然后将 a1联接到逆转后的链表的表尾(即a2)之后。
1 //递归方法逆转 单链表 2 Node* RecReverseList(Node* head) 3 { 4 if(!head || !head->next) 5 { 6 return head; 7 } 8 9 Node *newhead = RecReverseList(head->next); 10 head->next->next = head; 11 head->next = NULL; 12 return newhead; 13 } 14 15 //非递归方式逆转 单链表 16 Node* RecReverseList(Node* head) 17 { 18 if(!head || !head->next) 19 { 20 return head; 21 } 22 Node* p1 = head; 23 Node* p2 = p1->next; 24 head->next = NULL; 25 26 while(p2) 27 { 28 p1 = p2; 29 p2 = p2->next; 30 p1->next = head; 31 head = p2; 32 } 33 return head; 34 }
