Вернуть k-й с конца узел односвязного списка за один проход
Дан head односвязного списка. Верните узел на позиции k с конца (k = 0 — последний узел). Верните nil, если k вне диапазона.
Ограничения:
- Список односвязный — назад идти нельзя.
- Стремитесь к одному проходу: O(n) время, O(1) доп. память.
type Item struct {
val int
next *Item
}
func kthFromEnd(k int, head *Item) *Item {
// ваш код здесь
}Допишите реализацию.
Два указателя с разрывом k. Сначала продвиньте lead на k шагов вперёд; если он сошёл со списка раньше, k вне диапазона — верните nil. Затем двигайте lead и trail (старт с head) вместе, пока lead не дойдёт до последнего узла. trail теперь k-й с конца. Один проход, O(n) время, O(1) память — без предподсчёта длины и без второго обхода.
- ✗Предподсчитывать длину и обходить дважды вместо одного прохода двумя указателями
- ✗Забывать вернуть
nil, когдаkпревышает длину списка - ✗Утверждать, что стек или рекурсия дают O(1) память, хотя это O(n)
- →Как обнаружить, что
kвне диапазона, во время форы указателяlead? - →Почему инвариант разрыва в
kсохраняется, пока оба указателя идут вместе?
Решение
func kthFromEnd(k int, head *Item) *Item {
lead := head
// Фора в k шагов; если список короче — k вне диапазона.
for i := 0; i < k; i++ {
if lead == nil {
return nil
}
lead = lead.next
}
if lead == nil {
return nil
}
trail := head
// Двигаем оба, пока lead не встанет на последний узел.
for lead.next != nil {
lead = lead.next
trail = trail.next
}
return trail
}Как работает. Между lead и trail поддерживается разрыв в k узлов. Когда lead дошёл до последнего узла, trail отстаёт ровно на k — это и есть k-й с конца.
Сложность. Один проход: O(n) время, O(1) память. Предподсчитывать длину или обходить список второй раз не нужно.
Корнер-кейсы. k = 0 вернёт последний узел; k ≥ длины — nil.
