今日,我们看另一个链表任务。
建立一个函数来合拼 2 个已排序的链表。结论目录应当是应用 2 个目录的节点排序的目录。
因此,我们将应用上一篇文章里的通用链表实现,能够在这里找到
funcmergeSortedLists(ll1LinkedList[int],ll2LinkedList[int])LinkedList[int]{
result:=LinkedList[int]{}
p1:=ll1.Head
p2:=ll2.Head
rp:=&Node[int]{}//dummynodeasresulthead
result.Head= rp
forp1!=nil&&p2!=nil{
ifp1.Data>=p2.Data{
rp.Next=p2
p2=p2.Next
}else{
rp.Next=p1
p1=p1.Next
}
rp= rp.Next
}
ifp1!=nil{
rp.Next=p1
}
ifp2!=nil{
rp.Next=p2
}
result.Head=result.Head.Next
returnresult
}
逻辑很好理解。最先,大家设定偏向2个目录和结果目录头部表针。因为我们不知道结论列表的“头”,所以我们创建一个虚拟节点做为占位符(稍候我们将修补该节点)。大家更为结论目录创建一个当前节点 rp。
下面,大家迭代这 2 个目录。每个目录都有一个当前节点。在每一步中,我们都要查询 2 个当前节点中哪一个具备较小的值,并将该节点放进结论页面上。再将该列表的当前节点(较小的节点)移到列表中的下一个节点。还需要将结果的当前节点挪动到下一个部位。
我们的循环逻辑仅仅执行此操作,直至抵达其中一个列表的结尾。这时,我们知道其中一个目录不再有可较为元素;它们已经在结论页面上。因而,大家可以简单地将另一个列表的剩下节点放到过程的结尾,因为我们知道它们已经排列了。
你能怎样做这不同的事情?大家可以优化这个吗?请于评论中跟我说。
感谢!
本文及其本系列全部文章代码能够在这里找到
以上就是合拼排列目录的详细内容,大量请关注其他类似文章!