Задача: №19. Remove Nth Node From End of List
Сложность: medium

Учитывая заголовок связанного списка, удалите n-й узел с конца списка и верните его заголовок.

Пример:

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

👨‍💻 Алгоритм:

1⃣Создать фиктивный узел dummy, указывающий на head, чтобы удобно было обрабатывать крайние случаи (например, удаление головы).

2⃣Инициализировать два указателя fast и slow, оба на dummy. Сначала сдвинуть fast на n шагов вперёд.

3⃣Затем двигать оба указателя, пока fast.next не станет null. Теперь slow находится перед узлом, который нужно удалить.


😎 Решение:

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy;
        ListNode slow = dummy;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;

        return dummy.next;
    }
}

Ставь 👍 и забирай 📚 Базу знаний