链表就地逆置

1.
// 算法思想：逆置链表初始为空，表中节点从原链表中依次“删除”，
// 再逐个插入逆置链表的表头（即“头插”到逆置链表中），使它成
// 为逆置链表的“新”的第一个结点，如此循环，直至原链表为空。

void converse(LinkList *head)
{
    LinkList *p,*q;
    p=head->next;
    head->next=NULL;
    while(p)
    {
        /*向后挪动一个位置*/
        q=p;
        p=p->next;
        
        /*头插*/
        q->next=head->next;
        head->next=q;
    }
}

2.
// 算法思想：先假定有一个函数，可以将以head为头
// 结点的单链表逆序，并返回新的头结点。利用这个
// 函数对问题进行求解：将链表分为当前表头结点和
// 其余部分，递归的过程就是，先将表头结点从链表
// 中拆出来，然后对其余部分进行逆序，最后将当前
// 的表头结点链接到逆序链表的尾部。递归的终止条
// 件就是链表只剩一个节点时，直接返回这个节点


ListNode *reverse(ListNode *head)
{
    if(head==NULL || head->next ==NULL)
        return head;
 
    /*递归*/
    ListNode* headOfReverse = reverse(head->next);
    // cout<<head->next<<" "<<headOfReverse<<endl;
 
     /*回溯：将当前表头结点链接到逆序链表的尾部*/
     headOfReverse->next = head;
     head->next = NULL;
     return headOfReverse;
}