首页 > 文章列表 > Java程序删除循环链表开头的节点

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

java 删除 循环链表
457 2023-08-20

In this DSA problem, we will learn to create a circular linked list and delete the node from the beginning of that.

循环链表将最后一个节点与第一个节点相连接。要从链表中移除第一个节点,我们可以将第二个节点作为根节点,并将最后一个节点与第二个节点相连接。

问题陈述

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

示例示例

Input

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

Output

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

Explanation

We have deleted the node from starting.

Input

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

Output

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

Explanation

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

Approach 1

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

Algorithm

  • 步骤 1 - 创建一个包含整数数据类型的'value'和'next' listNode指针的'listNode'类。同时,定义构造函数来初始化'value'变量。

  • 第二步 - 接下来,定义 'root' 和 'last' 指针来存储链表的第一个和最后一个节点。

  • Step 3 − Now, define the addValue() function to add the node to the linked list.

  • Step 3.1 − Create a new listNode with the value we got as a parameter.

  • Step 3.2 − If the root node is NULL, assign a new node to the 'root' and 'last' node. Also, connect the new node with the root node.

  • 步骤 3.3 − 如果根节点不为空,则将新节点与最后一个节点连接起来,更新 'last' 指针的值,并将最后一个节点与根节点连接起来。

  • 第四步 - 定义deleteFirstNode()函数以从开头删除节点。

  • Step 4.1 − In the deleteFirstNode() function, If the root is null, execute the return statement.

  • 步骤 4.2 - 如果根节点和最后一个节点相同,则将根节点和最后一个节点更新为NULL。

  • 步骤 4.3 − 如果根节点和最后一个节点不相同,则将根节点更新为其下一个节点,并将最后一个节点与更新后的根节点连接。

  • Step 5 − Define the showList() function to print the list values.

  • Step 5.1 − Initialize the 'temp' node with the root node.

  • Step 5.2 − If the root is NULL, print the message that 'List is empty'.

  • 步骤 5.3 − 否则,遍历列表,并打印“temp”节点的值。同时,更新“temp”节点为其下一个节点。

  • Step 6 − In the main() method, create the object of the Main class.

  • Step 7 − By taking the object of Main class as a reference, execute the addValue() method to add nodes to the linked list. After that, call the showList() to show the original list.

  • 第8步 - 接下来,执行deleteFirstNode()函数来删除第一个节点,并调用showList()方法来显示更新后的链表。

Example

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

Output

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
  • 时间复杂度 - O(1),因为我们在常数时间内修改指针。

  • Space complexity − O(1) as we don't use dynamic space.

We learned to delete the first node from the circular linked list. The programmer may learn to delete the last node of the circular linked list. In this case, programmers need to connect the last-second element of the linked list with the root node.