Я предполагаю, что ваш код был изменен из кода для объединения двух списков.Вы должны вспомнить, почему каждый фрагмент кода работает, и подумать, почему ваш код работает не так, как вы думаете.
Предположим, что ваш оригинальный алгоритм выглядит следующим образом:
public ListNode LinkedTest(ListNode first, ListNode second) {
ListNode head = null;
if (first == null)
return second;
else if (second == null)
return first;
else if (first.data < second.data)
{
head = first;
head.next = LinkedTest(first.next, second);
}
else if (second.data < first.data)
{
head = second;
head.next = LinkedTest(first, second.next);
}
return head;
}
Первая половина метода проверяет необходимость завершения рекурсии.Здесь код завершается, когда один из двух списков достиг конца.Например, если вы объединяете список [1, 3, 5, 7] со списком [2, 4, 6, 8, 9, 10], вы в конечном итоге объедините список [] со списком [8, 9, 10].В этот момент вам нужно будет завершить работу, вернув список и, следовательно, завершив рекурсию.
Внесенные вами изменения в алгоритм неверны, поскольку при трехстороннем слиянии вы не можете просто вернуть второй список, когдаВ первом списке нет узлов.Критерии завершения стали более сложными, и вам следует обратить внимание на то, когда вам действительно нужно прекратить рекурсию.Например, если у вас есть попытка объединить [1, 2], [3, 4], [5, 6], предполагая, что другая часть алгоритма работает, то вы получите объединение между [], [3, 4], [5, 6] для которого вы собираетесь вернуть [3, 4] и отбросить [5, 6], что неверно.
Одним из решений является вызов двухсписочной версии алгоритма, когда какой-либо один список отсутствует.Это требует больше кода (что также довольно повторяющееся), но более простое, исходя из этого конкретного кода.Другое решение состоит в том, чтобы завершать только тогда, когда два списка пусты, но это требует особой осторожности в рекурсивном случае для проверки на нулевые значения.
Вторая половина метода сравниваетпервые элементы списков и использует меньший элемент в качестве заголовка нового списка, а затем назначает элемент данных next узла заголовка «каким бы ни был результат объединения остальных списков».Обратите внимание, что в этой версии кода каждый раз выполняется ровно один из блоков кода.(Если данные не равны, тогда будет ошибка. Исправление будет оставлено в качестве упражнения.) Пока рекурсия не завершена, нам нужно идти глубже, верно!
Модификация, которую выmade не работает, потому что вы сравниваете первые данные со вторыми данными, затем со вторыми и третьими .. тогда что?Давайте создадим таблицу, отследим код и запишем, как он ведет себя, и как бы вы хотели, чтобы код вел себя.
| Order | Your code | Expected | Result |
|-------|-------------|----------|---------|
| A<B<C | head = A | head = A | Correct |
| A<C<B | head = A | head = A | Correct |
| B<A<C | head = B | head = B | Correct |
| B<C<A | head = B | head = B | Correct |
| C<A<B | head = A | head = C | WRONG! |
| C<B<A | head = null | head = C | WRONG! | * note: no recursion in this case
Посмотрите, как ваш код дает сбой, когда C является наименьшим элементом?Вам тоже нужно это исправить.
Наконец, есть одно решение, которое даже не требует создания трехстороннего слияния.Технически, merge(A, merge(B, C)) все еще должен работать за O (n), сложность также ведет себя правильно.
Удачи в финале!