Задача: 1171. Remove Zero Sum Consecutive Nodes from Linked List
Сложность: medium

Дан указатель на голову связанного списка. Мы многократно удаляем последовательные последовательности узлов, сумма которых равна 0, до тех пор, пока такие последовательности не исчезнут.

После этого верните голову конечного связанного списка. Вы можете вернуть любой такой ответ.

Пример:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

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

1⃣Инициализируйте новый узел ListNode с именем front со значением 0, у которого поле next указывает на head, и узел start, указывающий на front.

2⃣Обрабатывайте все узлы в связанном списке, пока start != null. Инициализируйте переменную prefixSum значением 0 и узел ListNode с именем end, указывающий на start.next. Обрабатывайте остальные узлы в связанном списке, пока end != null: добавьте значение узла end к prefixSum. Если prefixSum равен 0, установите соединение от узла start к последнему узлу после последовательности с суммой ноль, установив start.next равным end.next. Установите end равным end.next.

3⃣Установите start равным start.next. Верните front.next. Узел front указывает на голову конечного связанного списка.

😎 Решение:

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    public ListNode RemoveZeroSumSublists(ListNode head) {
        ListNode front = new ListNode(0, head);
        ListNode start = front;

        while (start != null) {
            int prefixSum = 0;
            ListNode end = start.next;

            while (end != null) {
                prefixSum += end.val;
                if (prefixSum == 0) {
                    start.next = end.next;
                }
                end = end.next;
            }

            start = start.next;
        }
        return front.next;
    }
}

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