Вопрос:

Вам дается head связанного списка. Удалите средний узел и верните элемент head измененного связанного списка.

Средний узел связанного списка размером n – это узел ⌊n / 2⌋th из начала, использующий индексацию на основе 0, где ⌊x⌋ – наибольшее целое число. меньше или равно x.

  • Для n = 1, 2, 3, 4 и 5 средними узлами являются 0, 1, 1, 2 и соответственно.

Пример 1:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node.

Решение:

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

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

Наш первый шаг — проверить, содержит ли список только один элемент.

if(head -> next == NULL)
    return NULL;

Затем мы укажем медленный и быстрыйуказатель на головусписка. Будет создан еще один указатель, prev, который будет использоваться для отслеживания медленного указателя.

медленныйуказатель будет на один шаг опережать предыдущий.

ListNode* slow = head;
ListNode* fast = head;
ListNode* prev;

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

while(fast != NULL && fast -> next != NULL)
{
    prev = slow;
    slow = slow -> next;
    fast = fast -> next -> next;
 }

В конце присвойте значение next следующего узла удаляемого узла next из prev и верните голова.

prev -> next = prev -> next -> next;
    return head;

Ниже приведен полный код для данной проблемы:

Спасибо за прочтение!

S.