递归反转链表

// 单链表节点的结构
 class ListNode
 {
    public:
    int val;
    ListNode* next;
    ListNode(int x)
    {
        val = x;
        next = NULL;
    }
 };

 ListNode*reverse(ListNode* root, ListNode* &head)
 {
     if (root->next == NULL)
     {
         head = root;
         return root;
     }
     else
     {
         ListNode* tmp = root->next;
         root->next = NULL;
         ListNode* node = reverse(tmp,head);
         node->next = root;
         return root;
     }
 }

 ListNode* reverse2(ListNode* head) {
     if (head->next == NULL)
         return head;
     ListNode* last = reverse2(head->next);
     head->next->next = head;
     head->next = NULL;
     return last;
 }

 void test()
 {
     ListNode* node1 = new ListNode(1);
     ListNode* node2 = new ListNode(2);
     ListNode* node3 = new ListNode(3);
     ListNode* node4 = new ListNode(4);
     ListNode* node5 = new ListNode(5);
     node1->next = node2;
     node2->next = node3;
     node3->next = node4;
     node4->next = node5;
     ListNode* head = NULL;
     ListNode* ret = reverse(node1,head);
 }