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

javaobject oriented programmingprogramming更新于 2024/10/8 4:28:17

在这个 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 - 创建一个"listNode"类,其中包含整数数据类型的"值"和"下一个"listNode 指针。此外,定义构造函数来初始化"value"变量。

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

  • 步骤 3 - 现在,定义 addValue() 函数以将节点添加到链接列表。

  • 步骤 3.1 - 使用我们获得的值作为参数创建一个新的 listNode。

  • 步骤 3.2 - 如果根节点为 NULL,则将新节点分配给"root"和"last"节点。另外,将新节点与根节点连接起来。

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

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

  • 步骤 4.1 - 在 deleteFirstNode() 函数中,如果根为空,则执行 return 语句。

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

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

  • 步骤 5 - 定义 showList() 函数以打印列表值。

  • 步骤 5.1 - 使用根节点初始化"temp"节点。

  • 步骤 5.2 - 如果根为 NULL,则打印"列表为空"的消息。

  • 步骤 5.3 - 否则,遍历列表,并打印"temp"节点的值。此外,使用其下一个节点更新"temp"节点。

  • 步骤 6 - 在 main() 方法中,创建 Main 类的对象。

  • 步骤 7 - 通过将 Main 类的对象作为引用,执行 addValue() 方法将节点添加到链接列表中。之后,调用 showList() 显示原始列表。

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

示例

public class Main {

   // 创建链接列表的节点
   public class listNode {
      int value;
      listNode next;
      
      // 构造函数
      public listNode(int val) {
         this.value = val;
      }
   }
   
   // Root and last node initialization
   public listNode root = null;
   public listNode last = null;
   
   // 添加新节点的方法
   public void addValue(int val) {
   
    // 创建新的 listNode
    listNode newNode = new listNode(val);
    
    // 对于第一个节点
    if (root == null) {
        root = newNode;
        last = newNode;
        newNode.next = root;
    }
    
    // 在最后一个节点后添加新节点
    // 新节点指向根节点
    else {
        last.next = newNode;
        last = newNode;
        last.next = root;
    }
   }
   public void deleteFirstNode() {
   
      // 对于空列表
      if (root == null) {
         return;
      }
      
      // 根节点指向下一个节点。最后一个节点指向更新后的根节点
      else {
         if (root != last) {
            root = root.next;
            last.next = root;
         }
         
         // 对于具有单个节点的列表
         else {
            root = last = null;
         }
      }
   }
   
   // 显示节点
   public void showList() {
      listNode temp = root;
      if (root == null) {
         System.out.println("The list is empty");
      } else {
      
         // 遍历列表以显示每个节点的值
         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();
      
        // 将数据添加到列表
        list.addValue(1);
        list.addValue(2);
        list.addValue(3);
        list.addValue(4);
        list.addValue(8);
        list.addValue(10);
        
        // 打印原始列表
        System.out.println("初始列表为: - ");
        list.showList();
        
        // 删除第一个节点
        list.deleteFirstNode();
        System.out.println("删除第一个节点后,列表为: - ");
        list.showList();
        
        // 删除第二个节点
        list.deleteFirstNode();
        System.out.println("删除第二个节点后,列表为: - ");
        list.showList();
    }
}

输出

初始列表为: -
1 2 3 4 8 10
删除第一个节点后,列表为: -
2 3 4 8 10
删除第二个节点后,列表为: -
3 4 8 10
  • 时间复杂度 − O(1),因为我们在常数时间内修改指针。

  • 空间复杂度 − O(1),因为我们不使用动态空间。

我们学会了从循环链表中删除第一个节点。程序员可能会学会删除循环链表的最后一个节点。在这种情况下,程序员需要将链表的倒数第二个元素与根节点连接起来。


相关文章


有用资源