Question

数据结构算法问题

1.假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。
解： [题目分析]因为两个链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将较小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列，故在合并的同时，将链表结点逆置。
LinkList Union(LinkList la，lb)
//la、lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增次序排列
//本算法将两个链表合并成一个按元素值递减次序排列的单链表
{pa=la->next；pb=lb->next；//pa，pb分别是链表1a和lb的工作指针
la->next=null； //la作为结果链表的头指针，先将结果链表初始化为空
while(pa!=null&&pb!=null) //当两链表均不为空 时
if(pa->data<=pb->data )
{r=pa->next； //将pa的后继结点暂存于r
pa->next=la->next； //将pa结点链于结果表中，同时逆置
la->next=pa;
pa=r； //恢复pa为当前待比较结点
}
else
{r=pb->next；//将pb的后继结点暂存于r
pb->next=la->next；//将pb结点链于结果表中，同时逆置
la->next=pb；
pb=r；//恢复pb为当前待比较结点
}
while(pa!=null) //将la表的剩余部分链入结果表，并逆置
{r=pa->next；pa->next=la->next；la->next=pa；pa=r； }
while(pb!=null)
{r=pb->next；pb->next=la->next；la->next=pb；pb=r； }
}//算法Union结束

其中的逆置不太理解
pa->next=la->next； //将pa结点链于结果表中，同时逆置
la->next=pa;
我自己想想：la->next=pa->next
pa->next=la
求大婶解释

Answer 1

while(pa!=null) //将la表的剩余部分链入结果表，并逆置
{r=pa->next；pa->next=la->next；la->next=pa；pa=r； }
我就说这段吧~
下面那段lb有剩余是一样的。。。
首先可以肯定的是，la就是最后所求的的链表的头。
la是头结点，实际上没值，la->next的结点就是当前链表的最大值啦~~
先定义这个结点为point1，即point1=la->next，名字写长点，好区分。。。
然后，由于pa是剩余部分的第一个结点，所以pa的值，肯定大于la->next，
然后，pa的下一个是r，r的值肯定也是大于pa的。所以这3个结点的大小顺序应该是这样。
point1<pa<r，忽略等于的情况，因为题目说递增。。。
那最后的排列应该是r->pa->point1啦~~
所以，pa->next就是等于la->next了~~

追问

r值其实在一步逆置中大小是不知道的吧
r是用来寄存pa-next, 传递pa-next 比完一个pa,使pb可以继续与下一个pa比较