链表插入中间

Question

Node InsertNth(Node head, int data, int position) {


    Node start,curr,temp;
    start=head;
    curr=start;
    if(start==null)
        {
        temp=new Node();
        temp.data=data;
        temp.next=null;
        return head;
    }
    else if(position==0)
        {
        temp=new Node();
        temp.data=data;
        temp.next=start;
        return head;
    }
    else
        {
        for(int i=0;i<position;i++)
            {
            System.out.println("i:"+i);
            curr=start;
            start=start.next;
        }
        temp=new Node();
        temp.data=data;
        curr.next=temp;
        temp.next=start;
        return head;
    } 
}

在上面的代码中，我在 for 循环中打印了 "i" 的值。在控制台中，我得到的输出为

i:0
i:0
i:1
i:0
i:1
i:2
i:3

和

Exception in thread "main" java.lang.NullPointerException
    at Node.InsertNth(Solution.java:49)
    at Solution.main(Solution.java:88)

为什么 "i" 没有正确递增？如果它确实有效，那么我可以在中间进行插入。

Answer 1

问题不在于 for 循环，问题在于：方法被调用了 3 次

我刚刚将您的部分代码更改为：

else
{
    int count =0;
    for(int i=0;i<position;i++)
        {
        try{
        System.out.println("i :" +i);
        curr=start;
        start=start.next;
            count++;
        }
        catch(Exception e){

        }
    }
    System.out.println("count: " +count);

    temp=new Node();
    temp.data=data;
    curr.next=temp;
    temp.next=start;
    return head;
}

并在 hackerrank 中提交并打印：

i :0
count: 1
i :0
i :1
count: 2
i :0
i :1
i :2
i :3
count: 3

正在打印

    System.out.println("count: " +count);

3 次表示您的方法被调用三次，而不是您所想的一次。

为了编写正确的代码，只需确保 start 在 for 循环中不为 null。我没有尝试更改您的代码，只是添加了使其工作所需的内容。

Node InsertNth(Node head, int data, int position) {
     Node start,curr,temp;
     start=head;
     curr=start;
     if(start==null || position == 0)
     {
        temp=new Node();
        temp.data=data;
        temp.next=start;
        head=temp;
        return head;
     }
     else
    {
        for(int i=0;i<position && start!=null ;i++)
        {
         curr=start;
         start=start.next;
        }
        temp=new Node();
        temp.data=data;
        curr.next=temp;
        temp.next=start;
        return head;
    } 
 }

Answer 2

首先，为什么前两种情况是return head;？ temp 是列表的新头，应该返回。

其次，你的循环是正确的。但是，Hackerrank 运行多个测试用例。我输入了一个解决方案并在方法调用的开头插入了换行符。您只需执行三个测试用例。

i: 0

i: 0
i: 1

i: 0
i: 1
i: 2
i: 3

改进

您总是需要创建一个新节点，因此请重构它以使您的代码更简洁。
您不需要 start == null 检查，因为只要 position == 0.

插入改进后：

Node InsertNth(Node head, int data, int position) {
    Node temp = new Node();
    temp.data = data;
    Node start = head;
    Node curr = start;
    if (position == 0)
    {
        temp.next = start;
        return temp;
    } 
    else
    {
        for(int i = 0; i < position; i++)
        {
            curr=start;
            start=start.next;
        }
        curr.next=temp;
        temp.next=start;
        return head;
    } 
}

链表插入中间

Linked List Insertion in the middle

java

linked-list

insertion

data-structures

改进