Сортировка слиянием с функцией вставки

Question

У меня есть два отсортированных связанных списка l1 и l2. Я хотел объединить l2 в l1, сохраняя l1 отсортированным. Мой оператор возврата отсортирован по l1, а l2 - пустой список. Как мне подойти к этой проблеме с помощью функций insert_before, insert_after и remove_node? Есть идеи?

Answer 1

Если вы знаете, как реализованы связанные списки, вы можете легко выполнить итерацию по обоим спискам, используя что-то вроде описанного ниже. Если вы не знаете слишком много о связанных списках, вы можете сначала прочитать их.

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 подобная реализация, она перебирает оба списка и объединяет их вместе go. Я решил вернуть только l1, так как пустой список будет несколько бесполезным, верно?, Всех неэффективных вызовов get () можно избежать, написав собственный простой класс LinkedList, чтобы получить доступ к следующим и последним полям, что значительно облегчит навигацию.

Если бы вы могли предоставить дополнительную информацию о методах, которые у вас есть, или о языке, на котором это должно быть написано, я мог бы дать вам более подробные объяснения.

Редактировать: Пояснение

сначала обоим элементам elemA / elemB присваивается значение первого элемента в связанных списках, а затем l oop используется для их итерации до тех пор, пока не будут использованы значения индекса чтобы отследить, где мы находимся в списках, они слишком велики (например, == размер списка)

Теперь первые два оператора if должны проверять, прошел ли один из списков полностью итерацию, если это это случай для первого списка, следующий элемент второго списка просто добавляется за последним элемент l1, так как он должен быть больше его, иначе indexA не был бы увеличен. (В этом случае оператор indexA также увеличивается, поскольку размер списка увеличивается, а indexA сравнивается с l1.size ()), и, наконец, оператор continue переходит к следующей итерации l oop.
. Второй оператор if в while l oop проверяет, был ли второй список уже полностью повторен, если это правда, объединять больше нечего, поэтому оператор l oop останавливается оператором break.

ниже, более или менее classi c mergesort;
, если текущий элемент l1 меньше текущего элемента l2, просто go до следующего элемента l1 и go до следующей итерации l oop, в противном случае вставьте текущий элемент l2 перед elemA и выполните дальнейшую итерацию, здесь indexA также увеличивается, потому что в противном случае он больше не указывал бы на правый элемент, поскольку элемент был вставлен перед ним.
этого достаточно?

Редактировать: добавлено тестирование, если один из списков является нулевым, как предложено @ itwasntme

Answer 2

Функции insert_before, insert_after и remove_node четко не определены в вопросе. Таким образом, если предположить, что один из параметров является ссылкой на «список», является ли другой параметр индексом, итератором или указателем на узел? Если списки представляют собой двусвязные списки, то имеет смысл, чтобы вторым параметром был итератор или указатель на узел (каждый узел имеет указатель на предыдущий узел, поэтому нет необходимости сканировать по индексу, чтобы найти предыдущий узел).

В случае с std :: list :: sort в Visual Studio он использует итераторы и std :: list :: splice для перемещения узлов в списке, используя итераторы для отслеживания начала и конца подсписков. во время сортировки слиянием. Версия std :: list :: splice, используемая std :: list :: sort, объединяет remove_node и insert_before в одну функцию.