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

Tags: Easy Linked List

Links: https://leetcode-cn.com/problems/delete-n-nodes-after-m-nodes-of-a-linked-list/

---

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.

Follow up question: How can you solve this problem by modifying the list in-place?

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 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.

Example 3:

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

Example 4:

Input: head = [9,3,7,7,9,10,8,2], m = 1, n = 2
Output: [9,7,8]

Constraints:

• The given linked list will contain between 1 and 10^4 nodes.
• The value of each node in the linked list will be in the range [1, 10^6].
• 1 <= m,n <= 1000

---

每次让pre处在将要访问的节点之前，保留的部分用pre去探测，注意应该是先移动pre，然后判断pre是否为空指针，顺序不能翻转，不然会在下面的测试用例出错：

[6,3,5,6,2,8,9,2,3,4]
2
1

然后删除的部分用cur去探测，每次让cur指向pre的后面一个节点即可，仍然是先移动cur再判断。

/**
 * 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) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        ListNode *dummy = new ListNode(-1); dummy -> next = head;
        ListNode *pre = dummy, *cur = dummy;

        while (true) {
            int cnt = 0;
            bool arriveEnd = false;
            while (cnt < m) {
                pre = pre -> next;
                if (!pre) { arriveEnd = true; break; }
                ++cnt;
            }

            if (arriveEnd) break;
            cur = pre;

            cnt = 0;
            while (cnt < n) {
                cur = pre -> next;
                if (!cur) { arriveEnd = true; break; }
                ListNode *tmp = cur;
                pre -> next = cur -> next;
                delete tmp; tmp = NULL;
                ++cnt;
            }
            if (arriveEnd) break;
        }

        ListNode *res = dummy -> next;
        delete dummy; dummy = NULL;
        return res;
    }
};