1474. Delete N Nodes After M Nodes of a Linked List

leetcode easy

#csharp#easy#leetcode#linked-list

Task

Вам дано начало связанного списка и два целых числа m и n.

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

Начните с головы как текущего узла.

Сохраните первые m узлов, начиная с текущего узла.

Удалите следующие n узлов.

Продолжайте повторять шаги 2 и 3, пока не достигнете конца списка.

Верните голову изменённого списка после удаления указанных узлов.

Пример:

Input: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3

Output: [1,2,6,7,11,12]

Explanation: Keep the first (m = 2) nodes starting from the head of the linked List (1 ->2) show in black nodes.

Delete the next (n = 3) nodes (3 -> 4 -> 5) show in read nodes.

Continue with the same procedure until reaching the tail of the Linked List.

Head of the linked list after removing nodes is returned.

C# solution

matched/original

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 DeleteNodes(ListNode head, int m, int n) {
        ListNode currentNode = head;
        ListNode lastMNode = head;
        while (currentNode != null) {
            int mCount = m, nCount = n;
            while (currentNode != null && mCount > 0) {
                lastMNode = currentNode;
                currentNode = currentNode.next;
                mCount--;
            }
            while (currentNode != null && nCount > 0) {
                currentNode = currentNode.next;
                nCount--;
            }
            lastMNode.next = currentNode;
        }
        return head;
    }
}

C++ solution

auto-draft, review before submit

#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 DeleteNodes(ListNode head, int m, int n) {
        ListNode currentNode = head;
        ListNode lastMNode = head;
        while (currentNode != null) {
            int mCount = m, nCount = n;
            while (currentNode != null && mCount > 0) {
                lastMNode = currentNode;
                currentNode = currentNode.next;
                mCount--;
            }
            while (currentNode != null && nCount > 0) {
                currentNode = currentNode.next;
                nCount--;
            }
            lastMNode.next = currentNode;
        }
        return head;
    }
}

Java solution

matched/original

class Solution {
    public ListNode deleteNodes(ListNode head, int m, int n) {
        ListNode currentNode = head;
        ListNode lastMNode = head;
        while (currentNode != null) {
            int mCount = m, nCount = n;
            while (currentNode != null && mCount != 0) {
                lastMNode = currentNode;
                currentNode = currentNode.next;
                mCount--;
            }
            while (currentNode != null && nCount != 0) {
                currentNode = currentNode.next;
                nCount--;
            }
            lastMNode.next = currentNode;
        }
        return head;
    }
}

JavaScript solution

matched/original

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

var deleteNodes = function(head, m, n) {
    let currentNode = head;
    let lastMNode = head;

    while (currentNode !== null) {
        let mCount = m, nCount = n;

        while (currentNode !== null && mCount > 0) {
            lastMNode = currentNode;
            currentNode = currentNode.next;
            mCount--;
        }

        while (currentNode !== null && nCount > 0) {
            currentNode = currentNode.next;
            nCount--;
        }

        lastMNode.next = currentNode;
    }
    return head;
};

Python solution

matched/original

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
        currentNode = head
        lastMNode = head

        while currentNode:
            mCount, nCount = m, n

            while currentNode and mCount > 0:
                lastMNode = currentNode
                currentNode = currentNode.next
                mCount -= 1

            while currentNode and nCount > 0:
                currentNode = currentNode.next
                nCount -= 1

            lastMNode.next = currentNode

        return head

Go solution

matched/original

type ListNode struct {
    Val  int
    Next *ListNode
}

func deleteNodes(head *ListNode, m int, n int) *ListNode {
    currentNode := head
    lastMNode := head

    for currentNode != nil {
        mCount, nCount := m, n

        for currentNode != nil && mCount > 0 {
            lastMNode = currentNode
            currentNode = currentNode.Next
            mCount--
        }

        for currentNode != nil && nCount > 0 {
            currentNode = currentNode.Next
            nCount--
        }

        lastMNode.Next = currentNode
    }
    return head
}

Explanation

Algorithm

Инициализация указателей:

Инициализируйте currentNode на голову связанного списка. Этот указатель будет использоваться для линейного прохода по каждому узлу списка.

Инициализируйте lastMNode на голову связанного списка.

Итерация по списку:

Итеративно удаляйте n узлов после m узлов, продолжая до конца списка.

Проходите m узлов, обновляя lastMNode на текущий узел. После m итераций lastMNode указывает на m-й узел.

Продолжайте итерацию по n узлам.

Удаление узлов:

Чтобы удалить n узлов, измените указатель next у lastMNode, чтобы он указывал на currentNode после пропуска n узлов.

😎