237. Delete Node in a Linked List

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 → 2 → 3 → 4 and you are given the third node with value 3, the linked list should become 1 → 2 → 4 after calling your function.

237. Удаление вершины из связанного списка

Напишите функцию, которая удаляет вершину (кроме хвоста) в односвязном списке, если Вы имеете доступ только к его голове.

Пусть список имеет вид 1 → 2 → 3 → 4, а Вы хотите удалить третий элемент со значением 3. Тогда после вызова функции список примет вид 1 → 2 → 4.

class Solution {

public:

void deleteNode(ListNode* node) {

}

};

РЕШЕНИЕ

структуры данных – связный список

Анализ алгоритма

Нам не известна длина списка, но сказано что хвост удалять нельзя. Следовательно, список состоит из более чем одного элемента (возможно даже двух). Поэтому будем удалять голову списка.

Поскольку функции удаления передается сам указатель на голову списка, а не ссылка на него, то передвигать в другую область памяти node мы не можем (нельзя делать так, чтобы node указывала на другой объект в памяти, так как в этом случае будет передвигаться локальная копия указателя, а не глобальная).

Рассмотрим односвязный список:

Установим указатель p на второй элемент. Скопируем содержимое второго элемента списка в первый. То есть скопируем его значения val и next.

Удалим элемент списка, на который указывает p.

Получилось, что мы удалили первый элемент списка, хотя физически удалялся второй.

Реализация алгоритма

class Solution

{

public:

void deleteNode(ListNode* node)

{

ListNode* p = node->next;

node->val = node->next->val;

node->next = node->next->next;

delete p;

}

};

Если бы функции передавалась ссылка на указатель, то удалить первый элемент списка можно было бы так:

class Solution

{

public:

void deleteNode(ListNode* &node)

{

ListNode* p = node;

node = node->next;

delete p;

}

};