编写算法将带头结点的单链表就地逆置

问题描述：

试编写算法将带头结点的单链表就地逆置，所谓“就地”是指辅助空间为O(1)。

问题解答：

解法一：将头结点摘下，然后从第一结点开始，依次前插入到头结点的后面（头插法建立单链表)，直到最后一个结点为止，则实现了链表的逆置，如下图所示。

本题代码如下：

LinkList Reverse_l(LinkList &L){
    //L是带头结点的单链表，本算法将L就地逆置
    p=L->next;  //p为工作指针，从第一个元素结点开始
    L->next = NULL;  //先将头结点L的next域置为NULL
    while (p!=NULL) {  //依次将元素结点摘下
        r=p->next;  //暂存p的后继
        p->next=L->next;  //将p结点插入到头结点之后
        L->next=p;
        p=r;
    }
    return L;
}

解法二：大部分辅导书都只介绍解法一，这对读者的理解和思维是不利的。为了将调整指针这个复杂的过程分析清楚，我们借助图形来进行直观的分析。

假设pre、p和r指向3个相邻的结点，如下图所示。假设经过若千操作，*pre之前的结点的指针都已调整完毕，它们的next都指向其原前驱结点。现在令*p结点的next域指向*pre 结点，注意到一旦调整指针的指向后，*p的后继结点的链就断开了，为此需要用r来指向原 *p的后继结点。处理时需要注意两点：一是在处理第一个结点时，应将其next域置为NULL，而不是指向头结点（因为它将作为新表的尾结点）；二是在处理完最后一个结点后，需要将头结点的指针指向它。

本题代妈如下：

LinkList Reverse_2(LinkList &L){
    //依次遍历线性表L,并将结点指针反转
    LNode *pre,*p=L->next,*r=p->next;
    p->next=NULL;  //处理第一个结点
    while(r!=NULL) {  //r为空，则说明p为最后一个结点
        pre=p;  //依次继续遍历
        p=r;
        r=r->next;
        p->next=pre;  //指针反转
    }
    L->next=p;  //处理最后一个结点
    return L;
}

上述两个算法的时间复杂度为O(n)，空间复杂度为O(1)。