java在链表中的特定位置插入节点

Question

我需要在位置插入一个注释。我没有错，但我的答案是错的。你能帮我更正代码吗？ Link to question

Node InsertNth(Node head, int data, int position) {
    Node node = new Node();
    node.data = data;
 if (head == null){
        return node;
    } else {
    Node current = head;
    for (int i=0; i < position-1 ; i++){
        current = current.next;
    }

    node.next = current.next;
    current.next = node;
 return head;
}

}

Answer 1

使用指向头部的虚拟节点有助于减少许多检查：

Node insertNth(Node head, int data, int position) {
    Node dummy = new Node();
    dummy.next = head;

    Node runner = dummy;
    for (int i = 0; i < position; ++i) {
        runner = runner.next;
    }

    Node node = new Node();
    node.data = data;
    node.next = runner.next;
    runner.next = node;

    return dummy.next;
}

当然，递归解决方案也是可能的：

Node insertNthRecursive(Node head, int data, int position) {
    if (position == 0) {
        Node node = new Node();
        node.data = data;
        node.next = head;
        return node;
    }
    head.next = insertNthRecursive(head.next, data, position - 1);
    return head;
}

Answer 2

Node insertAt(Node head, int data, int position) {
    Node node = new Node();
    node.data = data;
    if (position == 0) {
        node.next = head;
        return node;
    } else {
        head.next = insertAt(head.next, data, position - 1);
        return head;
    }
    /* Or iterative
    Node current = head;
    Node previous = null;
    for (int i = 0; i < position && current != null; i++) {
        previous = current;
        current = current.next;
    }
    node.next = current;
    if (previous == null) {
        head = node;
    } else {
        previous.next = node;
    }
    return head;
    */
}

这不执行IndexOutOfBoundsException