найти средний элемент связанного списка

[АццкоМото]

Вообще, что характерно, у наивного подхода - пройти по списку полтора раза - ровно та же сложность, что и у подхода с двумя указателями.

[rzen]

для списка не нужна последовательная память (одно из редких преимуществ списка)

вот тут сердечно соглашусь

[Интеррапт]

Короче...

Code: Select all

struct node* findMiddle(struct node* head)
{
  struct node *slow_ptr = head;
  struct node *fast_ptr = head;
 
  if(head!=NULL) {
       while((fast_ptr->next)!=NULL &&
               (fast_ptr->next->next)!=NULL) {
          fast_ptr = fast_ptr->next->next;
          slow_ptr = slow_ptr->next;
       }
       return slow_ptr;
  } else {
    return NULL;
  }
}

А мне оттуда (http://www.geeksforgeeks.org/write-a-c- ... nked-list/) не приведенный тобой второй метод понравился (которым я тоже на интервью помнится писал, т.к. это стандартное решение), а третий метод:

Code: Select all

void printMiddle(struct node *head)
{
    int count = 0;
    struct node *mid = head;
 
    while (head != NULL)
    {
        /* update mid, when 'count' is odd number */
        if (count & 1)
            mid = mid->next;
 
        ++count;
        head = head->next;
    }
 
    /* if empty list is provided */
    if (mid != NULL)
        printf("\tThe middle element is %d\n\n", mid->data);
}

[valchkou]

Это по нашему, просили на яве, получили на с

[crypto5]

Если список двусвязный - то идти с обоих концов пока не встретятся.
Если односвязный, то не вижу ничего плохого что бы пройти вначале весь список, узнать размер, и потом пройти еще раз до половины.

[rzen]

Если список двусвязный - то идти с обоих концов пока не встретятся.

отличная мысль.

я ещё почесал репу и должен признать что в случае с вложенным циклом не полтора прохода получается а один проход. в этом смысле проход с двух концов даёт тот же результат. но мне нравится больше

[crypto5]

Если список двусвязный - то идти с обоих концов пока не встретятся.

отличная мысль.

я ещё почесал репу и должен признать что в случае с вложенным циклом не полтора прохода получается а один проход. в этом смысле проход с двух концов даёт тот же результат. но мне нравится больше

В вашем подходе(думаю вложенные циклы там все таки лишние, а имеется в виду то что реализовал Ацкомотто), вы факточески проходите полтора раза по списку, т.к. в первой части списка по каждому элементу проходит и быстрый указатель и медленный.

[Интеррапт]

Это по нашему, просили на яве, получили на с

Так имплементация почти одинаковая будет.

[Tarasik]

Да просто же. Точно также, как ищутся петли в связанном списке: начинается траверсал с начала двумя указателями, один передвигается на один элемент вперед, второй - на два. как второй уперся в конец, первый - в середине

Иначе петлю не найти без использования доплолнительной памяти. А вот в данном случае можно сначала пройти по списку чтоб узнать его длину O(N) если он не замкнутый на себя конечно а потом еще раз пройти O(n/2) чтоб взять средний. Что в лоб что по лбу.

Затраты будут те же O(n*3/2), что и если будем толкать два бегунка быстрый и медленный одновременно.

[АццкоМото]

А мне оттуда (http://www.geeksforgeeks.org/write-a-c- ... nked-list/) не приведенный тобой второй метод понравился (которым я тоже на интервью помнится писал, т.к. это стандартное решение), а третий метод:

Code: Select all

void printMiddle(struct node *head)
{
    int count = 0;
    struct node *mid = head;
 
    while (head != NULL)
    {
        /* update mid, when 'count' is odd number */
        if (count & 1)
            mid = mid->next;
 
        ++count;
        head = head->next;
    }
 
    /* if empty list is provided */
    if (mid != NULL)
        printf("\tThe middle element is %d\n\n", mid->data);
}

Ага, вроде и тот же хрен в другой руке, а гораздо элегантнее

[АццкоМото]

Да просто же. Точно также, как ищутся петли в связанном списке: начинается траверсал с начала двумя указателями, один передвигается на один элемент вперед, второй - на два. как второй уперся в конец, первый - в середине

Иначе петлю не найти без использования доплолнительной памяти. А вот в данном случае можно сначала пройти по списку чтоб узнать его длину O(N) если он не замкнутый на себя конечно а потом еще раз пройти O(n/2) чтоб взять средний. Что в лоб что по лбу.

Затраты будут те же O(n*3/2), что и если будем толкать два бегунка быстрый и медленный одновременно.

Да, Кэп, так и есть

[АццкоМото]

Это по нашему, просили на яве, получили на с

Просили приятеля, а написали на форуме. Это не смущает?
К тому же на яве тоже написали

[8K]

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

[Flash-04]

[valchkou]

Это по нашему, просили на яве, получили на с

Просили приятеля, а написали на форуме. Это не смущает?

Привык уже, и скоро си выучу, читая привет

[АццкоМото]

Это по нашему, просили на яве, получили на с

Просили приятеля, а написали на форуме. Это не смущает?

Привык уже, и скоро си выучу, читая привет

Ну так там же было на джаве; разница по сути в node.next вместо node->next а, ну и звездочки поубивать

[АццкоМото]

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

Ну, тогда как математик решает задачи.

Задача 1.
Дано - Плитка, кран, кастрюля
Цель - Вскипятить воды.
Решение - Открыть кран, набрать воды в кастрюлю, закрыть кран, поставить кастрюлю на плиту, включить ее

Задача 2.
Дано - Плитка, кран, кастрюля с водой на плите
Цель - Вскипятить воды.
Решение - вылить воду из кастрюли, свели к условиям задачи #1

[mr boombastic]

http://en.wikipedia.org/wiki/Cycle_detection

[poloko]

задали приятелю вопрос на интервью, ответ (от интервьюера) был такой, мол запустить цикл в цикле, внешний цикл по каждому элементу, внутренний через один, когда внутренний закончится, внешний как раз укажет на средний элемент.

а как бы вы такую задачу решили практически?

да, чуть не забыл, язык жаба.

Извиняюсь, но хотелось бы уточнить цель вопроса. Вам код или более эффективный алгоритм?

[fruit6]

задачка на здравый смысл. требуется написать код за 5 минут. я в пятницу попробовал ее на паре соискателей

[valchkou]

задачка на здравый смысл. требуется написать код за 5 минут. я в пятницу попробовал ее на паре соискателей

а никто не пробовал попросить написать любой код по желанию ?

[rzen]

задачка на здравый смысл. требуется написать код за 5 минут. я в пятницу попробовал ее на паре соискателей

а никто не пробовал попросить написать любой код по желанию ?

а смысл? вы ж не фантазёров на работу ищите.

[valchkou]

задачка на здравый смысл. требуется написать код за 5 минут. я в пятницу попробовал ее на паре соискателей

а никто не пробовал попросить написать любой код по желанию ?

а смысл? вы ж не фантазёров на работу ищите.

так разве та контора не фантазеров искала.
Ну есть уже на яве и size() и get(i) на связаном списке, в чем смысл спрашивать как бы вы изобрели свой велосипед ?
Правильно, только в том, чтобы выяснить вашу велосипедную изобретательность, а не умение использовать уже говый.

[rzen]

задачка на здравый смысл. требуется написать код за 5 минут. я в пятницу попробовал ее на паре соискателей

а никто не пробовал попросить написать любой код по желанию ?

а смысл? вы ж не фантазёров на работу ищите.

так разве та контора не фантазеров искала.
Ну есть уже на яве и size() и get(i) на связаном списке, в чем смысл спрашивать как бы вы изобрели свой велосипед ?
Правильно, только в том, чтобы выяснить вашу велосипедную изобретательность, а не умение использовать уже говый.

то что вопрос был дурацкий это одно, а то что кандидат должен сам себе придумывать вопросы это другое. разновидностей идиотизма как мы видим немало

[mikeG]

Нормальная задачка. На понимание связанных списков.
По моим наблюдениям, человек, решающий подобную задачу через size() и get(i), потом пишет такой код

for (i=0; i< list.size(); i++) {
if (list.get(i)==someObject) {....}
}