LeetCode 1474: Delete N Nodes After M Nodes of a Linked List

link

With (prev, curr) pointers, we skip m nodes and then delete n nodes.

Time: \mathcal{O}(\texttt{list-length}), space: \mathcal{O}(1).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def skip(self, prev, curr, k):
        while curr and k > 0:
            prev = curr
            curr = curr.next
            k -= 1
        
        return prev, curr

    def delete(self, prev, curr, k):
        while curr and k > 0:
            curr = curr.next
            k -= 1
        
        if prev:
            prev.next = curr

        return prev, curr


    def deleteNodes(self, head: Optional[ListNode], m: int, n: int) -> Optional[ListNode]:
        prev, curr = None, head
        while curr:
            prev, curr = self.skip(prev, curr, m)
            if not curr:
                break
            prev, curr = self.delete(prev, curr, n)

        return head

Leave a comment