Linked List - 跳过M个节点，之后删除N个节点

Question

我正在尝试解决这个代码挑战：

目标是遍历一个Linked List，跳过M个节点，然后删除N个节点，再跳过M个节点，再删除N个节点，如此循环直到链表结束。

例子

输入：

• 链表：1->2->3->4->5->6->7->8->null
• 男：2
• N：2

预期输出：

• 1->2->5->6->空

我的尝试

我做了一个函数

skipMdeleteN

来完成那个任务。

public class LinkedList{
    public static class Node{
        int data;
        Node next;
        public Node(int data){
            this.data=data;
            this.next=null;
        }
    }
    public static Node head;
    public static Node tail;

    public Node addFirst(int data){
        Node newNode=new Node(data);
        if(head==null){
            head=newNode;
            return head;
        }
        newNode.next=head;
        head=newNode;
        return head;
    }

    public static void print(LinkedList ll){
        Node temp=head;
        while(temp!=null){
            System.out.print(temp.data+"->");
            temp=temp.next;
        }
        System.out.print("null");
    } 

    //Delete N Nodes After M Nodes of a Linked List
    public static void skipMdeleteN(int M, int N, Node head){
        Node curr=head;
        Node ptr;
        for(int temp=1;temp<=M;temp++){
            curr=curr.next;
            if(temp==M){
                ptr=curr.next;
                for(int temp2=1;temp2<N;temp2++){
                    ptr=ptr.next;
                    if(temp2==N){
                        curr.next=ptr.next;
                        curr=ptr.next;
                    }
                } temp=1;
            }
        }
    }

    public static void main(String args[]){
        LinkedList ll=new LinkedList();
        head=ll.addFirst(8);
        head=ll.addFirst(7);
        head=ll.addFirst(6);
        head=ll.addFirst(5);
        head=ll.addFirst(4);
        head=ll.addFirst(3);
        head=ll.addFirst(2);
        head=ll.addFirst(1);
        
        
        print(ll);
        int M=2; int N=2;
        ll.skipMdeleteN(M,N,head);
        print(ll);
    }
}

问题

我得到这个例外：

1->2->3->4->5->6->7->8->nullException in thread "main" java.lang.NullPointerException: Cannot read field "next" because "<local4>" is null
        at LinkedList.skipMdeleteN(LinkedList.java:42)
        at LinkedList.main(LinkedList.java:66)

Answer 1

问题好像出在

skipMdeleteN

方法的实现上。您没有检查链表节点中的空值。具体来说，您假设链表中最后一个节点的

next

字段不为空。

要解决此问题，您可以在

skipMdeleteN

方法的开头添加空值检查，如下所示：

public static void skipMdeleteN(int M, int N, Node head){
    Node curr=head;
    Node ptr;
    while (curr != null) {
        for(int temp=1;temp<=M && curr != null;temp++){
            curr=curr.next;
            if(temp==M && curr != null){
                ptr=curr.next;
                for(int temp2=1;temp2<=N && ptr != null;temp2++){
                    ptr=ptr.next;
                }
                curr.next=ptr;
            }
        }
    }
}

有了这个实现，如果

curr

或

ptr

变为空，循环将终止，避免

NullPointerException

.

此外，请注意，我通过使用

while

循环而不是

for

循环并通过将

curr.next=ptr

语句移动到内部

for

循环之外来简化循环。这应该使代码更易于阅读和理解。

Answer 2

这段代码有几个问题：

• 错误的原因是一旦删除发生，你的循环执行

  temp=1;

  ，这使得外层循环永远继续下去，最终

  curr

  将是

  null

  并且

  curr.next;

  将触发异常。

• 你正在混合 instance 和 static 的东西。虽然你用 new LinkedList 创建了一个

  instance

  ，然后你继续使用静态方法和变量……这是错误的。一旦你创建了

  ll

  ，那个

  ll

  应该有实例成员来管理that particular列表的状态。所以

  head

  不应该是

  static

  ，也不应该是你的方法（除了

  main

  ），也不应该是

  Node

  类，......

• 您的代码没有防止在链表之外运行的保护措施，例如，当

  N

  或

  M

  的值远大于链表的大小时。

• 您的代码中没有规定将

  head

  更新为

  null

  ，以防

  M

  为零而

  N

  不是。

• 没问题，但更常见的是使用驼峰式命名变量，所以将

  n

  和

  m

  命名为小写。

这是对您的代码的更正：

public class LinkedList {
    public class Node{ // Not static
        int data;
        Node next;
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }
    public Node head; // Not static
    public Node tail; // Not static

    public void addFirst(int data) { // Not static, and void
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    public void print() { // Not static
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data+"->");
            temp=temp.next;
        }
        System.out.println("null");
    }

    // Following method should not be static, and not have head parameter
    public void skipMdeleteN(int m, int n) {
        if (n <= 0 || head == null) return; // Nothing to remove
        if (m == 0) { // Remove everything
            head = null;
            return; 
        }

        Node curr = head;
        while (curr != null) {
            for (int temp = 1; temp < m; temp++) {
                curr = curr.next;
                if (curr == null) return; // Nothing more to remove
            }
    
            Node ptr = curr;
            for (int temp = 0; temp <= n; temp++) {
                curr = curr.next;
                if (curr == null) break; // Prevent invalid access
            }
            ptr.next = curr; // Perform the removal
        }
    }
        
    public static void main(){
        LinkedList ll = new LinkedList();
        ll.addFirst(8); // Instance method, which should manage the head member
        ll.addFirst(7);
        ll.addFirst(6);
        ll.addFirst(5);
        ll.addFirst(4);
        ll.addFirst(3);
        ll.addFirst(2);
        ll.addFirst(1);
        
        ll.print(); // Instance method
        int m = 2; int n = 2;
        ll.skipMdeleteN(m, n); // No head argument
        ll.print(); // 1->2->5->6->null
    }
}