関小君刷题记

题目大意：

删除链表M个节点后的N个节点

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.

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

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1474

解题思路分析：

本题要求使用原地算法来完成对链表上某些节点的删除工作。换句话说我们不可以新建一个链表，然后再将原链表上需要保留的部分拷贝过来，这样空间复杂度会达到O(n)级别，即不符合原地算法要求。

实际上在原链表中直接删除节点难度并不大，我们可以使用递归或者循环方式来解题。以递归方法为例，递归函数中，我们使用两个变量m和n代表当前状态，当m大于0时，说明当前节点不需删除，将m减一递归至下一节点，递归的返回值为下一节点对象，并将该对象设置为当前节点的下一节点。当m等于0时，代表当前位置开始的节点需要被删除，因此我们不做任何处理，将n减一后递归至下一节点，递归的返回值为当前返回值。当m和0同时为0时，代表已经走完一组流程，此时将m和n复原，重复上述步骤。当前节点为空时递归终止。

实现代码：

int mm,nn;
public ListNode deleteNodes(ListNode head, int m, int n) {
    mm=m; // 将m和n保存为全局变量
    nn=n;
    return helper(head,m,n); // 递归求解
}

ListNode helper(ListNode head, int m, int n){
    if(head==null) return null; // 当前节点为空，返回空
    if(n==0){ // 如果以删除完n个节点，复原m和n值继续
        m=mm;
        n=nn;
    }
    if(m>0){ // 如果m大于0，当前元素需要保留
        // 当前节点的下一节点为递归返回值
        head.next=helper(head.next,m-1,n);
        // 返回当前节点
        return head;
    }else{ // 如果m等于0，当前元素需要删除
        // 递归到下一节点，递归返回之为当前返回值。
        return helper(head.next,m,n-1);
    }
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 58.76% of Java online submissions for Delete N Nodes After M Nodes of a Linked List.

Memory Usage: 48.8 MB, less than 100.00% of Java online submissions for Delete N Nodes After M Nodes of a Linked List.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1474-delete-n-nodes-after-m-nodes-of-a-linked-list-解题思路分析/