Удалить n-й элемент с конца в односвязном списке
Tags: algorithms, linkedlist, interview, twopointers
Published: 2023-07-24 11:06:43

**Задача**. Дан односвязный список. Нужно удалить n-й элемент с конца и вернуть голову списка в качестве результата. Можно считать, что n <= размер списка.
Например:
Список: [1,2,3,4,5], n = 2 -> [1,2,3,5]
Список: [1], n = 1 -> []
Список: [1, 2], n = 2 -> [1]

Ссылка на leetcode: https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/
**Решение**.

Класс ноды (элемента списка):
```java
public class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) { 
        this.val = val; 
    }

    ListNode(int val, ListNode next) { 
        this.val = val; 
        this.next = next; 
    }
 }
```
Если бы список был двусвязным (когда у нас есть ссылка на следующий и предыдущий элемент в списке), то задача бы была намного проще. Мы бы начали итерироваться с конца списка  и удалили бы n-й элемент. Но у нас список односвязный, у нас есть ссылка только на следующий элемент. Мы не можем итерировать с конца списка, только с начала.

Для решения применим метод, который называется **Two Pointers** (два указателя). Будем использовать одновременно два указателя для итерирования по списку. Первый назовем fast, второй slow.
Ключевая идея решения: вначале оба указателя указывают на начало списка. После отодвинем fast на n-элементов от slow (расстояние между fast и slow станет равным n). Далее будем одновременно двигать оба указателя, пока fast не достигнет конца списка. При этом slow будем указывать на n-й элемент с конца. Т.е. на тот элемент, который нам нужно удалить.
Посмотрим, как это будем работать на примере: [1, 2, 3, 4, 5], n = 2.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tu6j2zl0wl8ubsz7iagk.png)

Отодвинем fast на 2 элемента от slow:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/te3tpgcsot32wukwnrgr.png)

Далее будем одновременно двигать fast и slow, пока fast не достигнет конца списка. Также добавим указатель prev, который будет всегда указывать на предыдущий от slow элемент. Он нам понадобится для операции удаления:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vh3hffylxtepvx6j0dk4.png)

После первой итерации состояние указателей будет таким:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/41nb1m3xxfqp82a7lq75.png)

Когда fast достигнет конца списка:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i76j07qmjb1q7dbooljn.png)

Теперь удаляем элемент, на который указывает индекс slow. Для этого меняем ссылку на следующий элемент для prev: prev.next = slow.next:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e3nmkbfur7gtjblm8vs8.png)

Посмотрим, как это будет работать для edge-case, когда нам надо удалить голову списка:



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/idry9spi9ni4qv4xrorx.png)

Отодвинем fast от slow на 2 элемента:


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sbp136xkf0v71r4rqpng.png)

Далее будем одновременно двигать оба индекса, пока fast не достигнет конца списка. Но т.к. он уже в конце списка, то ничего двигать не надо. Надо просто удалить голову списка. При этом prev == null, поэтому удаление надо делать просто изменив указатель на начало списка: newHead = slow.next (или head = head.next):


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uibkkf4gl7c9isvwj7yo.png)


Код решения:



```java
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        ListNode slow = head;
        //Перемещаем fast указатель на расстояние n от slow
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        ListNode prev = null;
        //Итерируемся по списку до тех пор, пока fast не достигнет 
        //конца списка, а slow при этом будет указывать на n-й 
        //элемент с конца списка
        while (fast != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next;
        }
        //Edge-case, нужно удалить голову списка
        if (slow == head) {
            head = head.next;
            slow.next = null;
            return head;
        }
        // Удаляем n-й элемент списка с конца
        prev.next = slow.next;
        slow.next = null;
        return head;
    }
}
```