在链接列表中插入位置Java

人气:210 发布:2023-01-03 标签: java linked-list singly-linked-list

问题描述

我的问题是:编写一个函数,将一个新项插入到给定位置的整数链表中。 我的代码是:

public static SinglyLinkedListNode insert_at_position(SinglyLinkedListNode head, int val, int pos) {
    
        SinglyLinkedListNode temp = head;
        
        if (pos == 0)
        {
            SinglyLinkedListNode newNode = new SinglyLinkedListNode(val);
            newNode = temp;
            head = newNode;
        }
        
        else if (pos > 0)
        {
            SinglyLinkedListNode newNode = new SinglyLinkedListNode(val);
            newNode = temp;
            head = newNode;
            
            for (int i = 0 ; i <= pos; i++)
            {
                  temp = head.next;
                  if (i == pos)
                  {
                      head.next = newNode;
                      newNode = temp;
                  }  
            }
        }
        return head;
 }

我的代码只打印很多1。它有什么问题?

推荐答案

一些问题:

代码创建一个新节点,将其分配给newNode,然后立即将temp分配给newNode,从而丢失对新创建节点的引用

temphead的值初始化,然后newNode得到temp的值,然后head得到temp的值。这意味着您已将head设置为...head,即无操作。

循环在每次迭代中执行temp = head.next;。这将始终将相同的引用放入temp...每次它执行的时候。因此循环的迭代次数变得无关紧要。temp将始终引用列表中的第二个节点。这样做会更有意义temp = temp.next

在上次迭代中设置head.next = newNode;...即使忽略您对temp所做的操作。此赋值不使用在循环迭代期间所做的任何操作。它也可以在循环之外执行。

最后一条语句newNode = temp没有做任何有用的事情。newNode从未在该语句之后使用过,因此它也可能不在那里。如果是newNode.next = temp,那就更有意义了。这将有效地将newNode链接到可能的下一个节点。

循环迭代次数太多。因为您已经使用pos == 0在列表的开始处插入了新节点,所以pos == 1应该在head节点之后插入新节点,因此不需要迭代。仅当pos > 2需要迭代时。

以下是更正后的版本:

public static SinglyLinkedListNode insert_at_position(SinglyLinkedListNode head, 
                                                      int val, int pos) {        
    SinglyLinkedListNode newNode = new SinglyLinkedListNode(val);
    if (pos == 0) {
        newNode.next = head;
        head = newNode;
    } else if (pos > 0) {
        SinglyLinkedListNode temp = head;
        for (int i = 1; i < pos; i++) {
            temp = temp.next;
        }
        newNode.next = temp.next;
        temp.next = newNode;
    }
    return head;
}

19