数据结构 | 每日一练（42）

数据结构

合抱之木,生于毫末;九层之台,起于累土;千里之行,始于足下

——老子

1

每日一练

1． 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。

类似本题的另外叙述有：

（1）设有两个无头结点的单链表,头指针分别为 ha,hb,链中有数据域 data,链域 next,两链表的数据都按递增序存放,现要求将hb表归到ha表中,且归并后ha仍递增序,归并中ha表中已有的数据若hb中也有,则 hb 中的数据不归并到 ha 中,hb 的链表在算法中不允许破坏。

PROCEDURE merge(ha,hb);

（2）已知头指针分别为 la 和 lb 的带头结点的单链表中，结点按元素值非递减有序排列。写出将 la 和lb 两链表归并成一个结点按元素值非递减有序排列的单链表（其头指针为 lc），并计算算法的时间复杂度。

正确答案

ps：||代表注释

1．[题目分析]因为两链表已按元素值递增次序排列，将其合并时，均从第一个结点起进行比较，将小的链入链表中，同时后移链表工作指针。该问题要求结果链表按元素值递减次序排列。故在合并的同时，将链表结点逆置。

LinkedList Union(LinkedList la,lb)∥la,lb分别是带头结点的两个单链表的头指针，链表中的元素值按递增序排列，本算法将两链表合并成一个按元素值递减次序排列的单链表。

{ pa=la->next; pb=lb->next;∥pa，pb分别是链表la和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结束。

［算法讨论］上面两链表均不为空的表达式也可简写为 while(pa&&pb),两递增有序表合并成递减有序表

时，上述算法是边合并边逆置。也可先合并完，再作链表逆置。后者不如前者优化。算法中最后两个 while语

句，不可能执行两个，只能二者取一，即哪个表尚未到尾，就将其逆置到结果表中，即将剩余结点依次前插入

到结果表的头结点后面。

　与本题类似的其它题解答如下：

　（１）［问题分析］与上题类似，不同之处在于：一是链表无头结点，为处理方便，给加上头结点，处理

结束再删除之；二是数据相同的结点，不合并到结果链表中；三是hb链表不能被破坏，即将hb的结点合并到结

果链表时，要生成新结点。

　LinkedList Union(LinkedList ha, hb)

∥ha和hb是两个无头结点的数据域值递增有序的单链表，本算法将hb中并不出现在ha中的数据合并到ha中，

合并中不能破坏hb链表。

　｛LinkedList la;

la=(LinkedList)malloc( sizeof(LNode));

la->next=ha;∥申请头结点，以便操作。

pa=ha; ∥pa是ha链表的工作指针

pb=hb; ∥pb是hb链表的工作指针

pre=la; ∥pre指向当前待合并结点的前驱。

while(pa&&pb)

if(pa->data<pb->data)∥处理ha中数据

{pre->next=pa;pre=pa;pa=pa->next;}

else if(pa->data>pb->data)∥处理hb中数据。

{r=(LinkedList)malloc( sizeof(LNode));∥申请空间

r->data=pb->data; pre->next=r;

pre=r;∥将新结点链入结果链表。

pb=pb->next;∥hb链表中工作指针后移。

}

　　　　 else∥处理pa->data=pb->data;

{pre->next=pa; pre=pa;

pa=pa->next;∥两结点数据相等时，只将ha的数据链入。

pb=pb->next;∥不要hb的相等数据

}

if(pa!=null)pre->next=pa;∥将两链表中剩余部分链入结果链表。

else pre->next=pb;

free(la);∥释放头结点.ha,hb指针未被破坏。

}∥算法nion结束。

(2)本题与上面两题类似，要求结果指针为lc，其核心语句段如下：

pa=la->next;pb=hb->next;

lc=(LinkedList )malloc( sizeof(LNode));

pc=lc;∥pc是结果链表中当前结点的前驱

while(pa&&pb)

if(pa->data<pb->data)

{pc->next=pa;pc=pa;pa=pa->next;}

else {pc->next=pb;pc=pb;pb=pb->next;}

if(pa)pc->next=pa; else pc->next=pb;

free(la);free(lb);∥释放原来两链表的头结点。

算法时间复杂度为O（m+n），其中m和n分别为链表la和lb的长度

如果您觉得本篇文章对您有作用，请转发给更多的人，点一下好看就是对小编的最大支持！

-end-