为什么下面的代码不能在链表中的特定位置插入节点？

Question

请看一下下面的代码，让我知道它出了什么问题？我试图在链表中的特定位置插入一个节点。我们需要在插入头部节点后返回它的引用。

Node InsertNth(Node head, int data, int position) {
    Node newNode = new Node();
    newNode.data = data;

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

    while(position > 0 && head.next!=null){
        head = head.next;
        position -= 1;
    }

    newNode.next = head;
    head = newNode;
    return first;

}

Answer 1

是的，有点不对劲。在while循环之后，您试图在头之前插入新节点，但这不起作用。行head=newNode 是无用的。

要么你需要另一个指针指向头之前的节点，这样你就可以在这两个指针之间插入新节点，要么你需要停止，同时在循环一步之前，在头之后插入新节点。下面是第二个解决方案：

 while(position > 1 && head.next!=null){ //0 is replaced by 1 here
    head = head.next;
    position -= 1;
}

newNode.next = head.next;
head.next = newNode;
return first;

[编辑]

在这个解决方案中，您需要处理当位置等于0时的特殊情况，方法是在而循环之前添加以下代码：

if(position==0) {
    newNode.next = head.next;
    return newNode;
}