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

Problem Description

In this problem, you are given a singly linked list and two integers m and n. The task is to modify the linked list by iterating through it and alternating between keeping and removing nodes. To be precise, you have to keep the first m nodes, then remove the next n nodes, and continue this pattern until the end of the list. The outcome should be the head of the linked list after these operations have been performed.

Intuition

The intuition behind the solution is to effectively use two pointers to traverse the linked list: one to mark the boundary of the nodes that will be retained (pre) and the other to find the boundary where the removal will stop (cur). The general approach is:

Keep a pointer to the current node we're looking at, starting with the head of the list.
Move this pointer m-1 times forward (since we want to keep m nodes, we move m-1 times to stay on the last node that we want to keep).
Establish another pointer at the same position and move it n times forward to find the last node that we want to remove.
Connect the mth node to the node right after the last removed node (effectively skipping over n nodes).
Continue this process until we reach the end of the list.

This algorithm is an in-place transformation which means we modify the original linked list without using extra space for another list.

Learn more about Linked List patterns.

Solution Approach

The solution to this problem follows a straightforward iterative approach, using a simple while loop to traverse the linked list, removing unwanted nodes as it goes. Below are the steps involved in the implementation:

Initialize a pointer named pre to point to the head of the list. This pointer will be used to track the node after which node deletion will start.
Use a while loop that continues until pre is not None (meaning we have not reached the end of the list).
Within the while loop, process keeping m nodes intact by iterating m-1 times with a for loop. The -1 is used because we are starting from the node pre which is already considered the first of the m nodes. If during this process pre becomes None, we exit the loop because we've reached the end of the list.
Now, we need a second pointer called cur which will start at the same position as pre and move n times forward to mark the count of nodes to be deleted.
After the for loop to remove n nodes, set pre.next to cur.next, this effectively skips over n nodes that are to be deleted. If cur is None at the end of the for loop, it means we reached the end of the list, and thus, we can safely set pre.next to None.
Finally, move pre to pre.next to process the next batch of nodes, beginning the m-n cycle again.

This solution employs no additional data structures, effectively making it an in-place operation with O(1) additional space complexity. The time complexity is O(L) where L is the number of nodes in the linked list, as each node is visited at most once.

The pattern used is the two-pointer technique, where one pointer (pre) is used to keep track of the node at the border between kept and removed nodes, and the other (cur) used to find the next node that pre should point to after removing n nodes.

A side note is that we have to manage the case when we reach the end of the list correctly. If cur becomes None after the removal loop, it means that we do not have any more nodes to process, and we should break out of the loop.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a linked list and use a small example to illustrate the solution approach. Suppose our linked list is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 and the integers m and n are given as m = 2 and n = 3. This means we want to keep 2 nodes and then remove the next 3 nodes, repeating this process until the end of the list.

Start with the head of the list. The list is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8.
The pointer pre starts at the head node 1. We iterate m-1 times forward, which in this case is 1 time (since we are keeping two nodes, 1 and 2).
Now pre is at node 2. Next, we set up cur to point to the same node as pre.
We then move cur n times forward. Since n is 3, we move cur to node 5.
The list now looks like this, where the brackets indicate the nodes that will remain: [1 -> 2] 3 -> 4 -> 5 -> 6 -> 7 -> 8.
We connect the node at pre (which is node 2) to cur.next (which is node 6). Our list is now 1 -> 2 -> 6 -> 7 -> 8.
Now, we move pre to pre.next which points to node 6. Then we repeat our process. Since there are fewer than m nodes left after pre, we do not continue and our final output is the list 1 -> 2 -> 6 -> 7 -> 8.

Here are the steps in detail:

Initialization: pre points to 1, and the list is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8.
Iteration 1:
- Keep m nodes: pre traverses 1 node and still points to 2.
- Remove n nodes: cur starts at 2 and traverses 3 nodes, ending up at 5.
- Skip n nodes: Connect 2 to 6.
- The list is now [1 -> 2] -> 6 -> 7 -> 8.
Move pre to pre.next: pre now points to 6.
Iteration 2:
- Since there are fewer than m nodes left after pre, and we cannot remove more nodes, the process stops.

The final list, after the in-place modifications, is 1 -> 2 -> 6 -> 7 -> 8.

Solution Implementation

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6
7class Solution:
8    def deleteNodes(self, head: ListNode, m: int, n: int) -> ListNode:
9        current_node = head
10      
11        # Iterate over the entire linked list
12        while current_node:
13            # Skip m nodes, these nodes will be retained
14            for _ in range(m - 1):
15                if current_node:
16                    current_node = current_node.next
17            # If we reach the end of the list, return the head as we don't have
18            # more nodes to delete
19            if current_node is None:
20                return head
21          
22            # Now current_node points to the last node before the deletion begins
23            to_delete = current_node.next
24          
25            # Skip n nodes to find the last node which needs to be deleted
26            for _ in range(n):
27                if to_delete:
28                    to_delete = to_delete.next
29          
30            # Connect the current_node to the node following the last deleted node
31            current_node.next = to_delete
32          
33            # Move to the next set of nodes
34            current_node = to_delete
35      
36        return head  # Return the modified list
37

1class Solution {
2  
3    /**
4     * Given a linked list, its head, and two integers m and n,
5     * this function deletes every n nodes in the list after keeping m nodes.
6     *
7     * @param head The head of the singly-linked list.
8     * @param m    The number of nodes to keep before deletion starts.
9     * @param n    The number of nodes to delete.
10     * @return The head of the modified list.
11     */
12    public ListNode deleteNodes(ListNode head, int m, int n) {
13        // 'currentNode' is used to traverse the linked list starting from the head.
14        ListNode currentNode = head;
15      
16        // Continue loop until 'currentNode' is null, which means end of the list.
17        while (currentNode != null) {
18            // Skip 'm' nodes but stop if the end of the list is reached.
19            for (int i = 0; i < m - 1 && currentNode != null; ++i) {
20                currentNode = currentNode.next;
21            }
22          
23            // If 'currentNode' is null after the for loop, we return the head
24            // as we reached the end of the list and cannot delete further nodes.
25            if (currentNode == null) {
26                return head;
27            }
28          
29            // 'nodeToBeDeleted' points to the node from where we start deletion.
30            ListNode nodeToBeDeleted = currentNode;
31          
32            // Advance 'nodeToBeDeleted' 'n' times or until the end of the list is reached.
33            for (int i = 0; i < n && nodeToBeDeleted != null; ++i) {
34                nodeToBeDeleted = nodeToBeDeleted.next;
35            }
36          
37            // Connect the 'currentNode.next' to the node after the last deleted node.
38            // If 'nodeToBeDeleted' is null, we've reached the end and thus set next to null.
39            currentNode.next = (nodeToBeDeleted == null) ? null : nodeToBeDeleted.next;
40          
41            // Move 'currentNode' ahead to process the next chunk of nodes.
42            currentNode = currentNode.next;
43        }
44      
45        // Return the head of the modified list.
46        return head;
47    }
48}
49

1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 *     ListNode() : val(0), next(nullptr) {}
7 *     ListNode(int x) : val(x), next(nullptr) {}
8 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9 * };
10 */
11class Solution {
12public:
13    ListNode* deleteNodes(ListNode* head, int m, int n) {
14        // previous_node will point to the last node before the sequence to be deleted
15        ListNode* previous_node = head;
16      
17        // Continue iterating through the linked list until we reach the end
18        while (previous_node) {
19            // Skip m nodes, but retain the last one before deletion begins
20            for (int i = 0; i < m - 1 && previous_node; ++i) {
21                previous_node = previous_node->next;
22            }
23          
24            // If we've reached the end, return the head as no deletion is needed
25            if (!previous_node) {
26                return head;
27            }
28          
29            // Skip n nodes starting from previous_node->next for deletion
30            ListNode* current = previous_node;
31            for (int i = 0; i < n && current; ++i) {
32                current = current->next;
33            }
34          
35            // Connect the previous_node to the node after the n nodes to be deleted
36            // If current is not nullptr, link to the node after the deleted sequence
37            // If current is nullptr, it means we've reached the end of the list, so we set it to nullptr
38            previous_node->next = (current ? current->next : nullptr);
39          
40            // Move the previous_node forward to start a new sequence
41            previous_node = previous_node->next;
42        }
43      
44        // Return the head of the modified list
45        return head;
46    }
47};
48

1// Definition for singly-linked list node
2class ListNode {
3    val: number;
4    next: ListNode | null;
5
6    constructor(val: number = 0, next: ListNode | null = null) {
7        this.val = val;
8        this.next = next;
9    }
10}
11
12/**
13 * Deletes nodes in a linked list following a pattern: keep 'm' nodes then delete 'n' nodes, repeating this process.
14 * @param head - The head of the singly-linked list.
15 * @param m - The number of nodes to keep.
16 * @param n - The number of nodes to delete.
17 * @returns The head of the modified linked list.
18 */
19function deleteNodes(head: ListNode | null, m: number, n: number): ListNode | null {
20    // previousNode will point to the last node before the sequence to be deleted
21    let previousNode: ListNode | null = head;
22
23    // Continue iterating through the linked list until the end is reached
24    while (previousNode) {
25        // Skip 'm' nodes, but retain the last one before deletion begins
26        for (let i = 0; i < m - 1 && previousNode; i++) {
27            previousNode = previousNode.next;
28        }
29
30        // If the end is reached, no further deletion is needed
31        if (!previousNode) {
32            return head;
33        }
34
35        // Skip 'n' nodes starting from previousNode.next for deletion
36        let currentNode: ListNode | null = previousNode;
37        for (let i = 0; i < n && currentNode != null; i++) {
38            currentNode = currentNode.next;
39        }
40
41        // Connect previousNode to the node after the 'n' nodes to delete
42        // If currentNode is not null, link to the node after the deleted sequence
43        // If currentNode is null, set the next of previousNode to null (end of list)
44        previousNode.next = currentNode ? currentNode.next : null;
45
46        // Move previousNode forward to start a new sequence
47        previousNode = previousNode.next;
48    }
49
50    // Return the head of the modified list
51    return head;
52}
53

Time and Space Complexity

Time Complexity

The time complexity of the given code involves iterating through each node of the linked list using two nested loops controlled by m and n. The outer while loop goes through each node, but the iteration is controlled by the logic that deletes every n following m nodes. Each node is visited at most once due to the nature of the single pass through the linked list. The for loop running m times and the for loop running n times are sequential and do not multiply their number of operations since they operate on different sets of nodes. Therefore, the time complexity of this function is O(m + n), for each group of m+n nodes, with a total of O(T/m+n * (m + n)) = O(T) where T is the total number of nodes in the linked list.

Space Complexity

As there are no additional data structures that grow with the input size, and the given code only uses a fixed number of variables to keep track of the current and previous nodes, the space complexity is constant. Therefore, the space complexity is O(1).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know