数据结构 链表合并的问题

2024-12-27 16:03:28
推荐回答(1个)
回答1:

这是将两个已经按从小到大排好序的连标合并成一个从小到大排序的链表

用中文描述一下上面那段代码就是:
传入数组A的头节点ah,数组B的头节点bh;

每个数组分别设定两个指针,其中编号pa1和pb1分别指向当前各自遍历的节点,pa2指向当前节点的前一个节点(因为是单向链表,插入操作必须要记录前一个节点,否则还要重新遍历),pb2于与pb1指向同一个节点,是为了在执行合并时做缓存指针用;

do{
第一个while块做的事情是在A中找出第一个比B当前节点num值大的节点,将pa1指向该节点;

接下来的if(pb1->num<=pa1->num)块,则是将当前pa1左边的所有节点连接到pb2的左边,因为上面的while我们已经知道,pa1左边的所有节点都小于pb2的节点了。

然后在数组B中寻找出最后一个比pa1小的节点,将pb1指向该节点,此时pb2节点指向数组B中第一个比pa1左边所有节点都大的节点。这个操作是需要多次递归这个do块来实现,此时其他参数不变,所以上面的while不会再执行。

将数组B中所有比pa1左边节点大,比pa1节点小的节点,插入到pa2与pa1之间。这个操作也是通过多次执行do块来实现的,一次只添加一个B节点到A中。

while{
当其中一个数组已经遍历完时,将另一个数组的剩余部分直接拼接到A数组后面,合并结束;
否则就循环执行上面do{}的操作


举一个例子:
A:{1,2,3,8,9,10}
B:{4,5,6,11,12,13}

第一次插入:
while执行完毕后:pa1 -> 8,pa2 ->3
查找数组B中比pa1大的节点(11)之前,逐个将B中比pa1小的节点添加到pa2后面
即将pb1与pb2之间的4、5、6,插入到pa1与pa2之间后

A:{1,2,3,4,5,6,8,9,10}
B:{11,12,13}
第二次插入:
while执行完毕后:pa1 -> 10, pa2 -> 9
此时满足了最后那个while的判断,所有A中元素都小于B,所以直接将B添加到pa1后面,合并结束

A:{1,2,3,4,5,6,8,9,10,11,12,13}
返回ah,ah自始至终都指向了两个数组中最小的那个节点,也就是合并后数组的第一个节点