1171. Remove Zero Sum Consecutive Nodes from Linked List

LeetCode medium оригинал: C# #csharp #leetcode #linked-list #medium #prefix-sum

LeetCode Static

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

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

Пример:

Input: head = [1,2,-3,3,1]

Output: [3,1]

Note: The answer [1,2,1] would also be accepted.

C# решение

сопоставлено/оригинал

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;
    }
}

C++ решение

auto-draft, проверить перед отправкой

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val=0, ListNode next=null) {
        this.val = val;
        this.next = next;
    }
}
class Solution {
public:
    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;
    }
}

Java решение

сопоставлено/оригинал

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

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;
    }
}

JavaScript решение

сопоставлено/оригинал

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

var removeZeroSumSublists = function(head) {
    let front = new ListNode(0, head);
    let start = front;

    while (start) {
        let prefixSum = 0;
        let end = start.next;

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

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

Go решение

сопоставлено/оригинал

type ListNode struct {
    Val  int
    Next *ListNode
}

func removeZeroSumSublists(head *ListNode) *ListNode {
    front := &ListNode{0, head}
    start := front

    for start != nil {
        prefixSum := 0
        end := start.Next

        for end != nil {
            prefixSum += end.Val
            if prefixSum == 0 {
                start.Next = end.Next
            }
            end = end.Next
        }

        start = start.Next
    }
    return front.Next
}

Algorithm

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

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

start.next

. Обрабатывайте остальные узлы в связанном списке, пока end != null: добавьте значение узла end к prefixSum. Если prefixSum равен 0, установите соединение от узла start к последнему узлу после последовательности с суммой ноль, установив

start.next

равным

end.next

. Установите end равным

end.next

Установите start равным

start.next

. Верните

front.next

. Узел front указывает на голову конечного связанного списка.

😎

Вакансии для этой задачи

Показаны активные вакансии с пересечением по тегам задачи.

Все вакансии

Активных вакансий пока нет.