Java 删除循环链表尾部的节点

在这个数据结构问题中，我们将学习如何删除循环链表的最后一个节点。

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

问题说明

给定一个包含N个节点的循环链表，任务是删除链表的最后一个节点。

示例

输入

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

输出

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

解释

我们删除最后一个节点。

输入

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

输出

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

解释

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

方法1

在这种方法中，我们将找到循环链表的倒数第二个节点。在遍历链表时，我们可以检查当前节点的下一个指针是否指向最后一个节点。如果是，当前节点是第二个节点，更新它的下一个指针为根节点，并将当前节点设置为最后一个节点。

步骤

步骤 1 - 为循环链表的节点定义 ‘listNode’ 类。在该类中定义一个字符串数据类型的 ‘value’ 变量和 ‘next’ 指针，均属于 listNode 类型。此外，还需要在构造函数中初始化变量的值。
步骤 2 - 定义 ‘root’ 和 ‘last’ 指针。
步骤 3 - 创建 addNode() 函数，用于向循环链表中添加节点。
步骤 3.1 - 在 addNode() 函数中，使用给定的值初始化新节点。
步骤 3.2 - 如果 root 指针为空，则将 root 和 last 节点更新为 null。同时，将新节点的 next 指针更新为 root 指针。
步骤 3.3 - 在其他情况下，连接最后一个节点和新节点，将新节点变为最后一个节点，并将更新后的最后一个节点连接到根节点。
步骤 4 - 创建 deleteLastNode() 函数，用于从链表中删除最后一个节点。
步骤 4.1 - 对于空链表，执行 return 语句。
步骤 4.2 - 当根节点和最后一个节点不相等时，遍历链表直到当前节点的 next 指针指向最后一个节点。
步骤 4.3 - 然后，将倒数第二个节点作为最后一个节点，并将其与根节点连接起来。
步骤 4.4 - 当根节点和最后一个节点相等时，将根节点和最后一个节点更新为 null。
步骤 5 - 创建 printList() 函数，用于打印链表的元素。
步骤 5.1 - 使用 do-while 循环遍历链表，直到 ‘temp’ 节点等于 ‘root’ 节点，并打印每个节点的值。
步骤 6 - 多次执行 addNode() 方法以向循环链表添加多个节点。
步骤 7 - 使用 printList() 方法打印初始链表。现在，执行 deleteLastNode() 函数以删除最后一个节点，并使用 printList() 方法显示更新后的链表。

示例

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();
   }
}

输出

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