编写算法将带头结点的单链表就地逆置
问题描述:
试编写算法将带头结点的单链表就地逆置,所谓“就地”是指辅助空间为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)。