Что хотят услышать интервьюеры:

Нужно показать, что слияние двух списков можно сделать одним проходом, не выходя за границы более короткого списка. Обычно это делается через два индекса и цикл while, после чего остаток более длинного списка добавляется отдельно. Важно уметь объяснить корректную обработку разных длин и сохранить линейную сложность.

Определение:

Слияние двух списков через while — это последовательный проход по обоим спискам одновременно с добавлением элементов в результирующий список по выбранному правилу. Если списки разной длины, цикл продолжается только пока оба индекса не дошли до конца, а оставшиеся элементы более длинного списка добавляются после цикла. Такой подход часто используют для объединения отсортированных списков или для попарной обработки элементов.

Пример использования:

Например, есть два отсортированных списка: [1, 3, 5] и [2, 4, 6, 8]. Нужно получить один отсортированный результат [1, 2, 3, 4, 5, 6, 8].

package main

import "fmt"

func mergeSorted(a, b []int) []int {
	result := make([]int, 0, len(a)+len(b))
	i, j := 0, 0

	for i < len(a) && j < len(b) {
		if a[i] <= b[j] {
			result = append(result, a[i])
			i++
		} else {
			result = append(result, b[j])
			j++
		}
	}

	for i < len(a) {
		result = append(result, a[i])
		i++
	}

	for j < len(b) {
		result = append(result, b[j])
		j++
	}

	return result
}

func main() {
	a := []int{1, 3, 5}
	b := []int{2, 4, 6, 8}
	fmt.Println(mergeSorted(a, b))
}

Пояснение кода:

Код не требует дополнительной структуры данных, кроме результирующего массива. Сначала создаются два индекса i и j, которые идут по двум спискам. Основной цикл for i < len(a) && j < len(b) работает, пока в обоих списках есть элементы. На каждой итерации выбирается меньший элемент и добавляется в результат. После завершения этого цикла один из списков может еще содержать элементы, поэтому два следующих цикла добавляют оставшиеся значения без сравнения.

Ключевые моменты:

Основная идея — идти по двум спискам одновременно и не выходить за границы массива.
Условие цикла должно проверять наличие элементов в обоих списках.
После основного цикла обязательно нужно дописать хвост более длинного списка.
Для отсортированных списков это дает O(n + m) по времени.
Дополнительная память обычно O(n + m), если создается новый результирующий список.
Для Go вместо while обычно используется for с явным условием, что эквивалентно while в других языках.

Как реализовать слияние двух списков через цикл while с разной длиной списков?