递归和非递归实现链表反转

//思路为将节点从前到后依次放到表头，最后最后的节点到了最前面,最前面的节点到了最后面
ListNode * ReverseList(ListNode * head)
{
   //如果链表为空或者链表中只有一个元素
   if(head==NULL || head->m_pNext==NULL)
       return head;
   ListNode * p=head->m_pNext;
   ListNode * q=head;
   while(p!=NULL)
   {
     q->m_pNext=p->m_pNext;//记录下p的下一个节点
     p->m_pNext=head;
     head=p;
     p=q->m_pNext;//准备将p的下一个节点放到表头
   }
   return head;
}

//递归方式
ListNode * ReverseList2(ListNode * head)
{
    //如果链表为空或者链表中只有一个元素
    if(head==NULL || head->m_pNext==NULL)
        return head;
    else
    {
       ListNode * newhead=ReverseList2(head->m_pNext);//先反转后面的链表
       head->m_pNext->m_pNext=head;//再将当前节点设置为其然来后面节点的后续节点
       head->m_pNext=NULL;
       return newhead;
    }
}