Java 从循环链表的开头删除节点

在这个DSA问题中，我们将学习如何创建一个循环链表，并从中删除开头的节点。

循环链表将最后一个节点连接到第一个节点。为了从链表中删除第一个节点，我们可以将第二个节点设置为根节点，并将最后一个节点连接到第二个节点。

问题陈述

我们已经有一个循环链表。我们需要删除链表的起始节点。

示例

输入

1 -> 2 -> 3 -> 4 -> 8 -> 10

输出

2 -> 3 -> 4 -> 8 -> 10

解释

我们已经从开始位置删除了节点。

输入

100 -> 103 -> 200 -> 99 -> 56 -> 78 -> 532

输出

103 -> 200 -> 99 -> 56 -> 78 -> 532

说明

已删除循环链表中的第一个节点。

方法1

在这个方法中，我们首先创建循环链表。在向链表添加节点时，我们将最后一个节点与根节点相连接。此外，在删除第一个节点时，我们将根节点的下一个节点作为根节点，并将最后一个节点与更新后的根节点相连接。

步骤

步骤 1 - 创建一个包含整数数据类型的’value’和’next’ listNode指针的’listNode’类。此外，定义构造函数来初始化’value’变量。
步骤 2 - 接下来，定义’root’和’last’指针来存储链表的第一个节点和最后一个节点。
步骤 3 - 现在，定义addValue()函数来添加节点到链表中。
步骤 3.1 - 使用传递的参数创建一个新的listNode。
步骤 3.2 - 如果根节点为NULL，将一个新节点赋值给’root’和’last’节点。并且将新节点与根节点连接起来。
步骤 3.3 如果根节点不为空，则将新节点与最后一个节点连接起来，更新 ‘last’ 指针的值，并将最后一个节点与根节点相连。
步骤 4 - 定义 deleteFirstNode() 函数以从开头删除节点。
步骤 4.1 - 在 deleteFirstNode() 函数中，如果根节点为空，则执行 return 语句。
步骤 4.2 - 如果根节点和最后一个节点相同，则将根节点和最后一个节点更新为 NULL。
步骤 4.3 - 如果根节点和最后一个节点不相同，则将根节点更新为其下一个节点，并将最后一个节点与更新后的根节点相连。
步骤 5 - 定义 showList() 函数以打印列表的值。
步骤5.1 - 用根节点初始化’temp’节点。
步骤5.2 - 如果根节点为空，则打印消息’列表为空’。
步骤5.3 - 否则，遍历列表，并打印’temp’节点的值。同时，将’temp’节点更新为其下一个节点。
步骤6 - 在main()方法中，创建Main类的对象。
步骤7 - 通过将Main类的对象作为引用，执行addValue()方法来向链表添加节点。然后，调用showList()方法来显示原始列表。
步骤8 - 接下来，执行deleteFirstNode()函数来删除第一个节点，并调用showList()方法来显示更新后的链表。

示例

public class Main {

   // Node for creating the linked list
   public class listNode {
      int value;
      listNode next;

      // Constructor
      public listNode(int val) {
         this.value = val;
      }
   }

   // Root and last node initialization
   public listNode root = null;
   public listNode last = null;

   // Method to add new Node
   public void addValue(int 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 deleteFirstNode() {

      // 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) {
            root = root.next;
            last.next = root;
         }

         // For a list having a single node
         else {
            root = last = null;
         }
      }
   }

   // displaying the nodes
   public void showList() {
      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.addValue(1);
      list.addValue(2);
      list.addValue(3);
      list.addValue(4);
      list.addValue(8);
      list.addValue(10);

      // Printing the original list
      System.out.println("The initial list is: - ");
      list.showList();

      // Delete the first node
      list.deleteFirstNode();
      System.out.println("After deleting the first node, the list is: - ");
      list.showList();

      // Delete the second node
      list.deleteFirstNode();
      System.out.println("After deleting the second node, the list is: - ");
      list.showList();
    }
}

输出

The initial list is: - 
 1 2 3 4 8 10
After deleting the first node, the list is: - 
 2 3 4 8 10
After deleting the second node, the list is: - 
 3 4 8 10