在LinkedList java中的特定元素之后插入

Question

我试图编写函数 insertAfter 将元素插入到 LinkedList 中的特定元素之后。下面是代码。 insertAfter 函数没有产生所需的输出。有人可以帮助我在下面的 insertAfter 函数中犯了什么错误吗？我需要纠正。

import java.util.Scanner;
import java.lang.Exception;
import java.lang.StringBuilder;
import java.util.ArrayList;
import java.util.*;
import java.util.regex.*;
import java.util.stream.Collectors;

class SingleLinkedList<T> 
{
    public class Node 
    {
        public T data;
        public Node nextNode;
    }
    
    public Node headNode;
    public int size;
    
    public SingleLinkedList()
    {
        headNode = null;
        size = 0;
    }
    
    public boolean isEmpty()
    {
        if (headNode == null)
        {
            return true;
        }
        return false;
    }
    
    public void insertAtHead(T data)
    {
        Node node = new Node();
        node.data = data;
        node.nextNode = headNode;
        headNode = node;
        size++;
    }
    
    public void insertAtEnd(T data)
    {
        if (isEmpty())
        {
            insertAtHead(data);
            return;
        }
        
        Node newNode = new Node();
        newNode.data = data;
        newNode.nextNode = null;
        
        Node last = headNode;
        while (last.nextNode != null)
        {
            last = last.nextNode;
        }
        
        last.nextNode = newNode;
        size++;
    }
    
    public void insertAfter(T data1, T data2)
    {
        if (isEmpty())
        {
            System.out.println("The list is empty");
            return;
        }
        
        Node insertNode = new Node();
        insertNode.data = data2;
        
        Node temp = headNode;
        while (temp.data != data1)
        {
            temp = temp.nextNode;
        }
        
        insertNode.nextNode = temp;
        temp = insertNode;
        size++;
        
        
    }
    
    public void printList()
    {
        if (isEmpty())
        {
            System.out.println("The list is empty.");
            return;
        }
        
        Node temp = headNode;
        System.out.println("List : ");
        while (temp.nextNode != null)
        {
            System.out.print(temp.data.toString() + "->");
            temp = temp.nextNode;
        }
        
        System.out.println(" null");
    }
}
  





public class Solution
{
  //static String originalString="AbcDef";
  
  
     
  
  
  // arguments are passed using the text field below this editor
  public static void main(String[] args)
  {
     SingleLinkedList<Integer> sll = new SingleLinkedList<>();
     sll.printList();
     for (int i = 0; i <= 10; i++)
     {
         sll.insertAtEnd(i);
         
         
     }

    sll.printList();    

     System.out.println("The size of the list is : " + sll.size);

     sll.insertAfter(3,72);
     
     sll.printList();

     System.out.println("The new size of the list is : " + sll.size); 
     
  
  }
}

在 insertAfter 函数中，我创建一个临时节点并分配 headNode 地址。然后，我创建一个 while 循环并遍历列表，直到到达数据元素，之后我需要插入并更新临时节点中的 nextNode 地址。一旦循环中断，我将新节点的下一个地址更新为临时节点，并使用新节点的地址更新临时节点地址。这对我来说似乎是正确的，但代码提供了以下输出。

The list is empty.
List :
0->1->2->3->4->5->6->7->8->9-> null
The size of the list is : 11
List :
0->1->2->3->4->5->6->7->8->9-> null
The new size of the list is : 12

Answer 1

您的

insertAfter

逻辑不正确。当遇到与 data1 具有相同值的节点时，您的

while

循环就会退出。然后，需要将新节点指向包含data1的节点的下一个值，并将包含data1的节点指向新添加的值为data2的节点。添加这个可以修复该错误。

insertNode.nextNode = temp.nextNode;
temp.nextNode = insertNode;

新的输出将是这样的：

0->1->2->3->72->4->5->6->7->8->9->空

只是为了回答您的第二个查询，是的，您可以使用指向前一个节点以及指向当前节点的指针在单链表中实现

insertBefore

。它看起来是这样的。请注意，为了简单起见，省略了错误处理。

public void insertBefore(T data1, T data2) {
        Node p = null;
        Node curr = headNode;
        while (curr.data != data1) {
            p = curr;
            curr = curr.nextNode;
        }

        Node insertNode = new Node();
        insertNode.data = data2;
        p.nextNode = insertNode;
        insertNode.nextNode = curr;
        size = size + 1;
    }

Answer 2

如果你想在 data1 之后插入，你的错误就在这里（insertAfter 方法）：

insertNode.nextNode = temp;
    temp = insertNode;

所以这是正确的代码：

Node next = temp.nextNode;
temp.nextNode = insertNode;
insertNode.nextNode = next;

Answer 3

//thank you after modification, it worked perfectly for me.
public void insertAfter(int data1, int data2) {
        if (isEmpty()) {
            System.out.println("The list is empty");
            return;
        }

        Node insertNode = new Node(data2);

        Node temp = head;
        while (temp.value != data1) {
            temp = temp.next;
        }

        insertNode.next = temp.next;
        temp.next = insertNode;
        size++;

    }