вернуть 5-й элемент из последнего в связанном списке?

ProgramBox

вернуть 5-й элемент из последнего в связанном списке?

Post author:admin
Запись опубликована:2 сентября, 2022
Post category:Вопросы по программированию

#c #linked-list

#c #связанный список

Вопрос:

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

  struct Node  
 {   
  int data;  
  Node * next;    
 };  
 Node *function( struct Node *head)   
 {    
    if ( ! head)   
    {   
        std::cout <<" no linked present";  
        return 0;  
    }  

    Node  *current, *temp;  
    temp = NULL;
    current = head;  
    int counter = 0;  
    while( current != NULL)   
    {
        counter   ;  
        current = current->next;   
        if( counter >= 5)   
        {
            if( temp == NULL)  
                temp = head;   
            else
            temp = temp->next;  
        }  

    }  
     return (temp);    
   }

ЕСЛИ у вас, ребята, есть лучшее оптимальное решение, пожалуйста, опубликуйте его здесь.
Спасибо всем
, Сэм

1. кстати, где temp объявлено?

2. @Vlad, спасибо, что указал на это. Я внес изменения

3. хорошо, с новым редактированием: вы забыли инициализировать temp с NULL помощью .

4. Спасибо всем за помощь и большое спасибо Владу и Нику за указание на мою глупую ошибку, которая дорого обошлась во время собеседования

5. Я не думаю, что здравомыслящий интервьюер будет основывать свое решение на том, объявили ли вы все временные значения. В реальной жизни первая попытка компиляции кода немедленно сообщит вам о неинициализированной переменной.

Ответ №1:

Для односвязного списка ваше решение должно быть оптимальным. Для двухсвязного списка вы могли бы перейти со спины.

Ответ №2:

Если вы исключите случай, когда список имеет длину менее 5 элементов, я бы сказал, что следующее решение немного более элегантное, но по сути это то же самое:

 Node *function( struct Node *head)  
{
   while ( head->next->next->next->next )
      head = head->next;
   return head 
}

С точки зрения производительности, для односвязного списка вы не можете сделать лучше, чем O(n) , поэтому все, что можно улучшить, — это читаемость.

Редактировать:

Влад сделал интересный момент в комментариях, что на каждой итерации цикла выполняется больше инструкций. Я считаю, что это неправильно, поскольку для доступа к указателю требуется только 1 инструкция asm. Однако в коде OP:

    counter   ;  
   current = current->next;   
   if( counter >= 5)   
   {
       if( temp == NULL)  
           temp = head;   
       else
           temp = temp->next;  
   }

выполняются ли инструкции в цикле. Это менее эффективно. Увеличение, 2 назначения указателей и 2 сравнения…

Оба являются O(n) , но для больших входных данных имеет значение, равно ли время 4 * n или 10 * n.

1. Ваше решение более элегантное, но делает больше на каждой итерации. Решение OP делает только два продвижения (и одно приращение, которое может быть устранено). Кроме того, решение OP может быть параметризовано, тогда как у вашего 5 жестко запрограммировано.

2. @Vlad Я обновлю свой ответ, пожалуйста, прочтите, возможно, вам это покажется интересным.

3. ну, чтобы быть более эффективным, я бы внес небольшие изменения в код OP: (1) увеличьте значение counter only if counter < 5 (в else предложении) (2) пропустите проверку if (temp == NULL) и инициализируйте temp head перед циклом (для этого потребуется одноразовая проверка, равен ли счетчик <5 или нет раньше return ). Таким образом, мы имеем: 2 косвенных доступа, 2 назначения и 1 сравнение на итерацию. В вашем случае у нас есть 5 косвенных обращений и 2 назначения на итерацию.

4. «для доступа к указателю требуется только 1 инструкция asm», конечно, но для косвенного указания указателя требуется доступ к памяти, что, поскольку мы обобщаем, намного хуже. Также все обращения будут зависеть друг от друга, в отличие от кода OPs. </pedantic>

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

Ответ №3:

Похоже, что это будет работать нормально. Единственная проблема заключается в том, что вы не объявили temp в своем коде и не инициализировали его значением NULL.

Метки: вернуть 5-й элемент из последнего в связанном списке?