Блог

В интервью меня попросили узнать значение во 2-м узле из среднего узла связанного списка? Они ожидали, что сделают это за O (n) временных затрат.

Я попытался дать ответ, чтобы получить средний элемент, используя O (n2). Но это не могло сильно помочь. Затем попытался сделать в O (n), используя медленные и быстрые указатели.

Узел медленный, быстрый;

     while (slow.next != null and fast.next.next != null){

    }
  

Например. Введите связанный список: 1 2 3 4 5 6 7 8 9
Выходной узел: 7

Потому что средний узел является 5 , а 2-й элемент из него является 7 .

Решения высоко ценятся.

 Node getSecondAfterMind(Node head) {
  Node slow = head, fast = head;
  while(fast.next.next != NULL) {
    slow = slow.next;
    fast = fast.next.next;
  }
  if slow.next!= NULL amp;amp; slow.next.next != NULL {
      return slow.next.next;
  }

   return NULL;
}
  

Одним из решений может быть:

1. Выполните итерацию по связанному списку от начала до конца и поместите ссылку на каждый элемент в List .
2. Когда вы нажмете на конец связанного списка, найдите индекс ( i ) среднего элемента на основе размера списка.
3. Увеличьте этот индекс на 2 ( i 2 ).
4. Следуйте ссылке из списка по индексу i 2
5. Вы получили элемент.

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

1. Получите средний индекс, разделив размер на 2
2. Увеличьте этот индекс на 2 (назовем его midPlusTwo )
3. Повторите связанный список и создайте счетчик.
4. Остановитесь, когда счетчик будет равен midPlusTwo

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

Таким образом, вы можете получить требуемый узел за O (1) пространство и O (N) временную сложность.

@sourabh1024 написал код. Взгляните.