Разворот односвязного списка за O(n) (память — O(1)) на Гугл Гоу
Вчера друг подвозил меня до дома, я решил, пока в пробке, попрограмировать на «Гоу». Практики давненько не было, язык уже начинает забываться, не модули, это ерунда, а сами конструкции, вот что неприятно.
Взял задачу — развернуть односвязный список за O(n) с константным ограничением на память. Задачу частенько дают на собеседованиях, как я слышал, говорят мало кто решает, решил посмотреть действительно ли это сложно. В уме прикинул, подумалось что нет, практика показала, что я не ошибся. В общем, выкладываю что получилось.
package main
import (
"os"
"bufio"
)
// тип для односвязного списка
type links struct {
Next *links
Value string
}
// вывод на печать односвязаного списка
func (chain *links) Print() {
for chain != nil {
os.Stdout.WriteString(chain.Value)
chain = chain.Next
}
}
// разворачиваем односвязный список за O(n)
func (chain *links) Reverse() *links {
if chain == nil || chain.Next == nil {
return chain
}
left, next := chain, chain.Next.Next
chain = chain.Next
left.Next = nil
for {
chain.Next = left
if next == nil {
break
}
left, chain, next = chain, next, next.Next
}
return chain
}
// Создаём список из чего-нибудь, умеющего выдавать по одной строке за раз
func CreateFromReader(readline func() *string) *links {
var chain, start *links = nil, nil
for {
if line := readline(); line != nil {
link := &links{ nil, *line }
if chain == nil {
chain, start = link, link
} else {
chain.Next, chain = link, link
}
} else {
return start
}
}
return nil
}
// Точка входа
func main() {
if len(os.Args) < 2 {
os.Exit(1)
}
f, err := os.OpenFile(os.Args[1], os.O_RDONLY, 0666)
if err != nil {
os.Exit(2)
}
defer f.Close()
r := bufio.NewReader(f)
CreateFromReader(
func() (*string) {
if line, e := r.ReadString('\n'); e == nil {
return &line
}
return nil
},
).Reverse().Print()
}
Список создаётся из файла, который нужно передать программе первым параметром. Вообще, вся реализация разворота — в методе Reverse класса links, остальное — заполнение структуры и вывод на печать. Оцените как мало надо кода, чтобы решить это задание.
Им, конечно же, сразу отказывают? Как можно не решить задачу, которая даже проще, чем сортировка пузырьком?
Комментарий для fulc.ru:
Легко.
Достаточно не [осо]знать (не догадаться (не прочитать где-то раньше)), что для «разворачивания» списка (а не массива) не надо копировать значения, а достаточно перевесить указатели.
Комментарий для Baka (в то, что OpenID работает, не верю…:
(Ещё в первый момент можно понять «развернуть» как «unfold», а не как «reverse» и задуматься, о чём это вообще. O_o)
Комментарий для fulc.ru:
Увы, нет. В Яндексе средний уровень гораздо выше, чем средний уровень программистов в Казани. Нужно выбирать из тех, что есть.
Комментарий для Baka (в то, что OpenID работает, не верю…:
Тяжело поверить, что хороший программист может до этого не догадаться.
Или воспользоваться своими навыками коммуникации и уточнить этот момент на собеседовании у меня.