java - 使用java在特定位置插入节点

Question

我正在解决在特定位置插入节点的黑客等级问题。我在这种情况下使用java，但我不断收到错误。而且我不知道如何解决它。我感谢您的帮助。这是我的解决方案:

/*`enter code here`
      Insert Node at a given position in a linked list 
      head can be NULL 
      First element in the linked list is at position 0
      Node is defined as 
      class Node {
         int data;
         Node next;
      }*/
Node InsertNth(Node head, int data, int position) {
         `enter code here`// This is a "method-only" submission. 
        // You only need to complete this method.

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

        if(position == 1){
            Node newNode = new Node();
            newNode.data = data;
            newNode.next = head;
            head = newNode;
            return head;
        }

        // we need to go to n - 1
        int counter = 0;
        Node currNode = head;
        Node prevNode = null;
        while(counter != position -1 && currNode.next != null){
            prevNode = currNode;
            currNode = currNode.next;
            counter++;

        }

        Node nNode = new Node();
        nNode.data = data;
        prevNode.next = nNode;
        nNode.next = currNode;

        return head;

        /* another solution */

    }

Result:
Exception in thread "main" java.lang.NullPointerException
    at Node.InsertNth(Solution.java:54)
    at Solution.main(Solution.java:89)

Answer 1

在您给出的代码片段中，您在注释中提到第一个元素位于位置 0。因此，如果插入发生在位置 0，则 head 将发生变化。因此，你所做的条件

if(position == 1){
            Node newNode = new Node();
            newNode.data = data;
            newNode.next = head;
            head = newNode;
            return head;
        }

你实际上应该检查位置== 0。你所说的输出中的不间断重复只是因为这个。例如，如果链表 10->20 ，我希望在位置 0 处插入 30 ，并且我们按照您的代码进行操作，那么我们将不会进入循环 0(counter) != -1 (position -1) 所以我们 prevNode 和 currNode现在两者都指向 10

        Node nNode = new Node();
        nNode.data = data;
        prevNode.next = nNode; // you made 10 point to 30
        nNode.next = currNode; // here you made 30 point to 10 so **loop** here