Вам дается 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.