LeetCode 1474. Delete N Nodes After M Nodes of a Linked List Solution in Java, C++, Python & More | Explanation + Code

Description

You are given the head of a linked list and two integers m and n.

Traverse the linked list and remove some nodes in the following way:

• Start with the head as the current node.
• Keep the first m nodes starting with the current node.
• Remove the next n nodes
• Keep repeating steps 2 and 3 until you reach the end of the list.

Return the head of the modified list after removing the mentioned nodes.

 

Example 1:

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.

Example 2:

Input: head = [1,2,3,4,5,6,7,8,9,10,11], m = 1, n = 3
Output: [1,5,9]
Explanation: Head of linked list after removing nodes is returned.

 

Constraints:

• The number of nodes in the list is in the range [1, 104].
• 1 <= Node.val <= 106
• 1 <= m, n <= 1000

 

Follow up: Could you solve this problem by modifying the list in-place?

Solutions

Solution 1: Simulation

We can simulate the entire deletion process. First, use a pointer pre to point to the head of the linked list, then traverse the linked list, moving m - 1 steps. If pre is null, it means the number of nodes from the current node is less than m, so we directly return the head. Otherwise, use a pointer cur to point to pre, then move n steps. If cur is null, it means the number of nodes from pre is less than m + n, so we directly set the next of pre to null. Otherwise, set the next of pre to the next of cur, then move pre to its next. Continue traversing the linked list until pre is null, then return the head.

The time complexity is O(n), where n is the number of nodes in the linked list. The space complexity is O(1).

PythonJavaC++GoTypeScript

# Definition for singly-linked list. # 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: pre = head while pre: for _ in range(m - 1): if pre: pre = pre.next if pre is None: return head cur = pre for _ in range(n): if cur: cur = cur.next pre.next = None if cur is None else cur.next pre = pre.next return head(code-box)

/** * 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 deleteNodes(ListNode head, int m, int n) { ListNode pre = head; while (pre != null) { for (int i = 0; i < m - 1 && pre != null; ++i) { pre = pre.next; } if (pre == null) { return head; } ListNode cur = pre; for (int i = 0; i < n && cur != null; ++i) { cur = cur.next; } pre.next = cur == null ? null : cur.next; pre = pre.next; } return head; } }(code-box)

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* deleteNodes(ListNode* head, int m, int n) { auto pre = head; while (pre) { for (int i = 0; i < m - 1 && pre; ++i) { pre = pre->next; } if (!pre) { return head; } auto cur = pre; for (int i = 0; i < n && cur; ++i) { cur = cur->next; } pre->next = cur ? cur->next : nullptr; pre = pre->next; } return head; } };(code-box)

/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func deleteNodes(head *ListNode, m int, n int) *ListNode { pre := head for pre != nil { for i := 0; i < m-1 && pre != nil; i++ { pre = pre.Next } if pre == nil { return head } cur := pre for i := 0; i < n && cur != nil; i++ { cur = cur.Next } pre.Next = nil if cur != nil { pre.Next = cur.Next } pre = pre.Next } return head }(code-box)

/** * Definition for singly-linked list. * class ListNode { * val: number * next: ListNode | null * constructor(val?: number, next?: ListNode | null) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } * } */ function deleteNodes(head: ListNode | null, m: number, n: number): ListNode | null { let pre = head; while (pre) { for (let i = 0; i < m - 1 && pre; ++i) { pre = pre.next; } if (!pre) { break; } let cur = pre; for (let i = 0; i < n && cur; ++i) { cur = cur.next; } pre.next = cur?.next || null; pre = pre.next; } return head; }(code-box)