Разворот односвязного списка за 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, остальное — заполнение структуры и вывод на печать. Оцените как мало надо кода, чтобы решить это задание.
12 декабря 2012 07:24

Fulcrum (fulc.ru)
13 декабря 2012, 16:04

говорят мало кто решает
Им, конечно же, сразу отказывают? Как можно не решить задачу, которая даже проще, чем сортировка пузырьком?

Baka (в то, что OpenID работает, не верю… (инкогнито)
13 декабря 2012, 21:20, ответ предназначен Fulcrum (fulc.ru):

Как можно не решить задачу, которая даже проще, чем сортировка пузырьком?
Легко.
Достаточно не [осо]знать (не догадаться (не прочитать где-то раньше)), что для "разворачивания" списка (а не массива) не надо копировать значения, а достаточно перевесить указатели.

Baka (в то, что OpenID работает, не верю… (инкогнито)
13 декабря 2012, 21:23, ответ предназначен Baka (в то, что OpenID работает, не верю…

(Ещё в первый момент можно понять "развернуть" как "unfold", а не как "reverse" и задуматься, о чём это вообще. O_o)

bolk (bolknote.ru)
14 декабря 2012, 06:15, ответ предназначен Fulcrum (fulc.ru):

Им, конечно же, сразу отказывают? Как можно не решить задачу, которая даже проще, чем сортировка пузырьком?
Увы, нет. В Яндексе средний уровень гораздо выше, чем средний уровень программистов в Казани. Нужно выбирать из тех, что есть.

bolk (bolknote.ru)
14 декабря 2012, 06:17, ответ предназначен Baka (в то, что OpenID работает, не верю…

Достаточно не [осо]знать (не догадаться (не прочитать где-то раньше)), что для «разворачивания» списка (а не массива) не надо копировать значения, а достаточно перевесить указатели.
Тяжело поверить, что хороший программист может до этого не догадаться.
Ещё в первый момент можно понять «развернуть» как «unfold», а не как «reverse» и задуматься, о чём это вообще.
Или воспользоваться своими навыками коммуникации и уточнить этот момент на собеседовании у меня.

Ваше имя или адрес блога (можно OpenID):

Текст вашего комментария, не HTML:

Кому бы вы хотели ответить (или кликните на его аватару)