问具有插入功能的合并排序

EN

如果您知道链表是如何实现的，那么您可以使用下面的方法轻松地遍历这两个链表。如果您对链表了解不多，那么您可能需要先阅读这些内容。

if(l1 == null || l2 == null){
    return l1==null ? l2 : l1;
indexA = indexB = 0;
elemA = l1.get(0);
elemB = l2.get(0);
while(indexA<l1.size() || indexB<l2.size()){   
    if(indexA==l1.size()){
        l1.insert_after(l1.size()-1,elemB);
        indexA++;
        indexB++;
        if(indexB<l2.size()){
            elemB = l2.get(indexB);
        }
        continue;
    }
    if(indexB==l2.size()){
        break;
    }
    if(elemA<elemB){
        indexA++;
        if(indexA<l1.size()){
            elemA = l1.get(indexA);
        }
        continue;
    }
    if(elemA>elemB){
        l1.insert_before(indexA,elemB);
        indexA++;
        indexB++;
        if(indexB<l2.size()){
            elemB = l2.get(indexB);
        }
}
return l1;

这是一个类似java的实现，它遍历两个列表，并在旅途中将它们合并在一起。我决定只返回l1，因为空列表有点没用，对吧?所有低效的get()调用都可以通过编写一个简单的LinkedList类来访问next和last字段来避免，这将极大地方便导航。

如果你能提供关于你可用的方法或写这篇文章的语言的更多信息，我可能会为你提供更好的解释。

编辑:说明

首先，两个列表都被赋予链表中第一个元素的值，然后使用while循环遍历它们，直到用于跟踪我们在列表中所处位置的索引值都太高(例如，==size of /elemB )

现在，前两个if语句将检查其中一个列表是否已经完全遍历，如果是第一个列表，则将第二个列表的下一个元素添加到l1的最后一个元素后面，因为它必须大于它，否则indexA不会增加。(在这个if语句中，indexA也是递增的，因为列表的大小越来越大，并且将indexA与l1.size()进行比较)，最后，continue语句跳到循环的下一次迭代。

while循环中的第二个if语句测试第二个列表是否已经完全迭代过，如果是这样，则没有更多要合并的内容，因此循环将由break语句停止。

下面是或多或少经典的合并排序；

如果l1的当前元素小于l2的当前元素，只需转到l1的下一个元素并进行下一次循环迭代，否则在elemA之前插入l2的当前元素并在此处进一步迭代，因为indexA也会递增，否则它将不再指向右侧的元素，因为在它之前插入了一个元素。

这足够了吗？

编辑:添加了@itwasntme建议的列表是否为空的测试

函数insert_before、insert_after和remove_node在问题中没有明确定义。因此，假设其中一个参数是对“列表”的引用，那么另一个参数是索引、迭代器还是指向节点的指针？如果列表是双向链表，那么第二个参数是迭代器或指向节点的指针(每个节点都有指向前一个节点的指针，因此不需要根据索引扫描来查找前一个节点)。

对于Visual Studio的std:: list :: sort，它使用迭代器和std::list::splice在列表中移动节点，并在合并排序期间使用迭代器跟踪子列表的开始和结束。由std::list::sort使用的std::list::splice版本将remove_node和insert_before组合成一个函数。