Question

单链表的就地逆置的算法！！

求大神解答单链表就地逆置的算法！！

Answer 1

就地逆置即算法的辅助空间为O(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;  
    }  
}

Answer 2

void List_inverse(LinkList &L)
{
    LinkList p,q;
    p=L->next;
    L->next=NULL;
    while(p!=NULL)
    {
        q=p->next;
        p->next=L->next;
        L->next=p;
        p=q;
    }    
}