主题：[讨论]链表的逆置
zhenwoliao
[专家分：130] 发布于 2006-03-24 21:24:00
各位大哥，大姐／
谁能给下单链表的逆置的算发呢＞不太明白咯！ 谢谢 ！＠
回复列表 （共4个回复）
板凳
海上飞洪 [专家分：520] 发布于 2006-03-25 02:56:00
void Inverse(LinkList &L)
{
LinkList p,q;
p=L->next;
L->next=NULL;
while(p)
{
q=p->next;
p->next=L->next;
L->next=p;
p=q;
}
}
你自己把图画出来,思路就很清晰了
3 楼
zhouchao221 [专家分：520] 发布于 2006-03-25 04:28:00
//将单链表逆置显示输出
bool Transdisplay(ListNode & L) const
{
//定义单链表指针
ListNode *q=L.first->link,*m;
//定义整型变量
int j,k=0,i=0;
//定义交换参数
Type bring;
//开始首尾颠倒
while(i<Length()/2)//保证恰好完全互换
{
j=0;//初始化变量j
m=L.first->link;//使单链表指针指向表头
while(j<Length()-i-1)//使单链表指针指向固定结点位置
{
m=m->link;//指向下一个结点
j++;//向目标结点靠近一步
}
//将处于单链表中第j位的结点中的值
//与处于倒数第j位的结点中的值互换
bring=q->data;
q->data=m->data;
m->data=bring;
//指向下一个结点
q=q->link;
i++;//目标结点前移一个
}
return true;//倒置成功返回true
}
4 楼
lijianqy [专家分：90] 发布于 2006-03-27 11:04:00
(1)算法
struct link
{
int data;
struct link *next;
};
link reverse(link x)
{
if( NULL==x )
return NULL;
link t=NULL;
link r=NULL, y=x; //(0)
while(y!=NULL)
{
t = y->next; //(1)
y->next = r; //(2)
r = y; //(3)
y = t; //(4)
}
return r; //返回逆置后的链表
}
(二)原理
(0)(1)(2)(3)(4)分别对应以上程序的各序号
第一次while循环
-------------------------------------------
(0) r=NULL, y=x
r=NULL a ---> b ---> c ---> d --> NULL
|(0)
y
-------------------------------------------
(1) t =y->next
r=NULL a ---> b ---> c ---> d --> NULL
|(0) | (1)
y t
--------------------------------------------
(2) y->next = r
a ---> NULL b ---> c ---> d --> NULL
|(0) (2) | | (1)
y r t
---------------------------------------------
(3) r = y
a ---> NULL b ---> c ---> d --> NULL
|(0) (2) | (1)
y t
|(3)
r
---------------------------------------------
(4) y = t
a ---> NULL b ---> c ---> d --> NULL
|(0) (2) | (1)
| t
|(3) | (4)
r y
第二次while循环(并对上面进行整理)
---------------------------------------------
(1) t = y->next
a ---> NULL b ---> c ---> d --> NULL
| | |(1)
r y t
---------------------------------------------
(2) y->next = r
b ---> a ---> NULL c ---> d --> NULL
| (2) | |(1)
y r t
---------------------------------------------
(3) r = y
b ---> a ---> NULL c ---> d --> NULL
| (2) |(1)
y t
| (3)
r
---------------------------------------------
(4) y = t
b ---> a ---> NULL c ---> d --> NULL
| (2) |(1)
| t
| (3) |(4)
r y
第三个循环 (并对上面的进行整理)
---------------------------------------------
(1) t = y->next
b ---> a ---> NULL c ---> d --> NULL
| | |(1)
r y t
以后的与第二次循环同, 最终可得:
d ---> c ---> b ---> a ---> NULL
我来回复
您所在位置：
