首页　>　文章列表　>　Java程序：从循环链表的末尾删除节点

Java程序：从循环链表的末尾删除节点

java 循环链表删除节点
305 2023-08-20

In this DSA problem, we will learn the remove the last node of the circular linked list.

我们将第二个最后一个节点的下一个指针设置为Null，以从常规链表中删除最后一个节点，但在循环链表中，我们需要将根节点设置为第二个最后一个节点的下一个指针。

Problem Statement

We have given a circular linked list containing the N nodes. The given task is to delete the last node of the linked list.

Sample Examples

输入

Hello -> World! -> How -> are -> You -> Doing?

Output

Hello -> World! -> How -> are -> You

Explanation

We remove the last node.

输入

23 -> 4 -> 67 -> 89 -> 73 -> 100

Output

23 -> 4 -> 67 -> 89 -> 73

Explanation

我们删除了最后一个节点。

方法一

In this approach, we will find the second-last node of the circular linked list. While traversing the linked list, we can check whether the next pointer of the current node points to the last node. If yes, the current node is the second node, update its next pointer with the root node, and make the current node the last node.

算法

Step 1 − Define the 'listNode' class for the node of the circular linked list. Also, define the 'value' variable of the string data type and the 'next' pointer of the listNode type in the class. Furthermore, initialize the variable values in the constructor.
Step 2 − Define the 'root' and 'last' pointers.
第三步 − 创建addNode()函数来向循环链表中添加一个节点。
Step 3.1 − In the addNode() function, initialize the new node with the given value.
步骤 3.2 - 如果根指针为空，则将根和最后一个节点更新为null。同时，将新节点的下一个指针更新为根指针。
Step 3.3 − In other cases, connect the last node with the new node, make the new node to the last node, and connect the updated last node to the root node.
步骤 4 − 创建 deleteLastNode() 函数来从链表中删除最后一个节点。
步骤 4.1 - 对于一个空列表，执行 return 语句。
步骤 4.2 − 当根节点和最后一个节点不相等时，遍历链表直到当前节点的下一个指针指向最后一个节点。
Step 4.3 − After that, make the second-last node to the last node, and connect it with the root node.
步骤 4.4 − 当根节点和最后一个节点相等时，使用 null 更新根节点和最后一个节点。
第5步 - 创建printList()函数以打印链表的元素。
步骤 5.1 - 使用do-while循环遍历列表，直到'temp'节点等于'root'节点，并打印每个节点的值。
Step 6 − Execute the addNode() method multiple times to add multiple nodes to the circular linked list.
Step 7 − Print the initial list using the printList() method. Now, execute the deleteLastNode() function to delete the last node and printList() method to show the updated list.

Example

public class Main {

   // Node for creating the linked list
   public class listNode {
      String value;
      listNode next;
      public listNode(String val) {
         this.value = val;
      }
   }
   
   // Root and last node initialization
   public listNode root = null;
   public listNode last = null;
   
   // Method to add new Node
   public void addNode(String val) {
   
      // Cerate new listNode
      listNode newNode = new listNode(val);
      
      // For the first node
      if (root == null) {
         root = newNode;
         last = newNode;
         newNode.next = root;
      }
      
      // Add new node after the last node. New node points to the root node
      else {
         last.next = newNode;
         last = newNode;
         last.next = root;
      }
   }
   public void deleteLastNode() {
   
      // For an empty list
      if (root == null) {
         return;
      }
      
      // Root node points to the next node. The last node points to the updated root node
      else {
         if (root != last) {
            listNode temp = root;
            while (temp.next != last) {
               temp = temp.next;
            }
            
            // Second last element is the new tail
            last = temp;
            last.next = root;
         }
         
         // For a list having a single node
         else {
            root = last = null;
         }
      }
   }
   
   // displaying the nodes
   public void printList() {
      listNode temp = root;
      if (root == null) {
         System.out.println("The list is empty");
      } else {
      
         // Traverse the list to show each node's value
         do {
            System.out.print(temp.value + " ");
            temp = temp.next;
         } while (temp != root);
            System.out.println();
      }
   }
   public static void main(String[] args) {
      Main list = new Main();
      
      // Adds data to the list
      list.addNode("Hello");
      list.addNode("World!");
      list.addNode("How");
      list.addNode("are");
      list.addNode("You");
      list.addNode("Doing?");
      
      // Printing the original list
      System.out.println("The initial list is :- ");
      list.printList();
      
      // Delete the first node
      list.deleteLastNode();
      System.out.println("After deleting the first node, the list is :- ");
      list.printList();
      
      // Delete the second node
      list.deleteLastNode();
      System.out.println("After deleting the second node, the list is :- ");
      list.printList();
   }
}

Output

The initial list is :- 
Hello World! How are You Doing? 
After deleting the first node, the list is :- 
Hello World! How are You 
After deleting the second node, the list is :- 
Hello World! How are