Даны два односвязных списка, отсортированных по неубыванию. Слейте их в один
отсортированный список и верните его голову.
type ListNode struct {
Val int
Next *ListNode
}
// MergeTwoLists сливает отсортированные списки a и b в один отсортированный.
func MergeTwoLists(a, b *ListNode) *ListNode
Примеры
a: 1 → 2 → 4, b: 1 → 3 → 4 → 1 → 1 → 2 → 3 → 4 → 4
a: nil, b: 0 → 0
a: nil, b: nil → nil
Требования
- Новые узлы не создавать: результат собирается из узлов
a и b перевязкой Next.
- Слияние устойчивое: при равных значениях сначала идут узлы из
a, а внутри каждого
списка порядок узлов сохраняется.
- Длины до 10⁶ каждая. O(n + m) времени, O(1) дополнительной памяти.
Разбор и эталонное решение — после своей попытки: на собеседовании подсказок не будет.
Сначала попробуй сам — подсказки не дают готовый ответ.