Java 程序从循环链表末尾删除一个节点

javaobject oriented programmingprogramming更新于 2024/10/8 5:00:17

在这个 DSA 问题中,我们将学习如何删除循环链表的最后一个节点。

我们将倒数第二个节点的下一个指针设置为 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"变量和 listNode 类型的"next"指针。此外,在构造函数中初始化变量值。

  • 步骤 2 - 定义"根"和"最后一个"指针。

  • 步骤 3 - 创建 addNode() 函数以将节点添加到循环链表。

  • 步骤 3.1 - 在 addNode() 函数中,使用给定值初始化新节点。

  • 步骤 3.2 - 如果根指针为空,则用空值更新根和最后一个节点。此外,使用根指针更新新节点的下一个指针。

  • 步骤 3.3 - 在其他情况下,将最后一个节点与新节点连接,将新节点设为最后一个节点,并将更新后的最后一个节点连接到根节点。

  • 步骤 4 - 创建 deleteLastNode() 函数以从链接列表中删除最后一个节点。

  • 步骤 4.1 - 对于空列表,执行 return 语句。

  • 步骤 4.2 - 当根节点和最后一个节点不相等时,遍历链接列表,直到当前节点的下一个指针指向最后一个节点。

  • 步骤 4.3 - 之后,将倒数第二个节点设为最后一个节点,并将其与根连接节点。

  • 步骤 4.4 - 当根节点和最后一个节点相等时,用 null 更新根节点和最后一个节点。

  • 步骤 5 - 创建 printList() 函数以打印链接列表的元素。

  • 步骤 5.1 - 使用 do-while 循环遍历列表,直到"临时"节点等于"根"节点,并打印每个节点的值。

  • 步骤 6 - 多次执行 addNode() 方法以将多个节点添加到循环链接列表中。

  • 步骤 7 - 使用 printList() 方法打印初始列表。现在,执行 deleteLastNode() 函数删除最后一个节点,并执行 printList() 方法以显示更新后的列表。

示例

public class Main {

   // 创建链接列表的节点
   public class listNode {
      String value;
      listNode next;
      public listNode(String val) {
         this.value = val;
      }
   }
   
    // 根节点和最后一个节点初始化
    public listNode root = null;
    public listNode last = null;
    
    // 添加新节点的方法
    public void addNode(String 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 deleteLastNode() {
   
      // 对于空列表
      if (root == null) {
         return;
      }
      
      // 根节点指向下一个节点。最后一个节点指向更新后的根节点
      else {
         if (root != last) {
            listNode temp = root;
            while (temp.next != last) {
               temp = temp.next;
            }
            
            // 倒数第二个元素是新的尾部
            last = temp;
            last.next = root;
         }
         
         // 对于具有单个节点的列表
         else {
            root = last = null;
         }
      }
   }
   
   // 显示节点
   public void printList() {
      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.addNode("Hello");
        list.addNode("World!");
        list.addNode("How");
        list.addNode("are");
        list.addNode("You");
        list.addNode("Doing?);
        
        // 打印原始列表
        System.out.println("初始列表为 :- ");
        list.printList();
        
        // 删除第一个节点
        list.deleteLastNode();
        System.out.println("删除第一个节点后,列表为 :- ");
        list.printList();
        
        // 删除第二个节点
        list.deleteLastNode();
        System.out.println("删除第二个节点后,列表为 :- ");
        list.printList();
   }
}

输出

初始列表为:-
Hello World! How are You Doing? 
删除第一个节点后,列表为:-
Hello World! How are You 
删除第二个节点后,列表为:-
Hello World! How are
  • 时间复杂度 - O(N),因为我们需要到达最后一个节点。

  • 空间复杂度 - O(1),因为我们不使用任何额外空间。

从循环链表中删除最后一个节点的逻辑部分是找到倒数第二个节点并将其与根节点连接起来。程序员可以尝试从循环链表中删除第一个节点以进行更多练习。


相关文章


有用资源