„Въпрос“:

Получавате 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.