Java 程序从循环链表的中间删除节点

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

在这个 DSA 问题中,我们将学习从循环链表中删除中间节点。

我们可以从循环链表中删除中间节点,就像我们从常规链表中删除中间节点一样。我们需要找到中间节点的前一个节点和下一个节点,并直接连接它们以删除中间节点。

问题陈述

我们有一个循环链表,需要从链表中删除中间节点。如果链表包含偶数个节点,则第 (N/2) 个节点为中间节点。

示例

输入

90 32 67 84 23 78

输出

90 32 84 23 78

说明

67 被删除,因为它是中间节点。

输入

90 32 84 23 78

输出

90 32 23 78

解释

84 被删除,因为它是中间节点。

方法 1

第一个任务是计算链接列表中的节点总数。如果总节点数为偶数,则删除第 (N/2) 个节点。否则,如果奇数总数为偶数,我们可以得到中间节点。

我们需要找到中间节点的前一个节点,并用中间节点的下一个指针值更新它的下一个指针值,以删除中间节点。

算法

  • 步骤 1 - 定义包含整数类型的"val"变量和"dataNode"类型的下一个指针的"dataNode"类。

  • 步骤 2 - 定义名为"listSize"的静态变量来存储链接列表的大小。此外,定义"root"和"end"指针来存储第一个和最后一个节点。

  • 步骤 3 - 接下来,定义类的构造函数,用 0 初始化"root"和"end"节点以及列表的大小。

  • 步骤 4 - 定义 addToList() 函数以将节点添加到循环链接列表。

  • 步骤 4.1 - 在 addToList() 函数中,使用给定值定义 dataNode 类型的"newNode"。

  • 步骤 4.2 - 如果根节点为空,则使用 newNode 更新根节点和结束节点。另外,用根节点更新 newNode 的下一个指针。

  • 步骤 4.3 - 否则,将最后一个节点的下一个指针指向 newNode。另外,更新"end"指针值,并用"root"节点更新最后一个节点的下一个指针。

  • 步骤 4.4 - 添加节点后,将"listSize"加 1。

  • 步骤 5 - 定义 middleDeletion() 函数以删除中间节点。

  • 步骤 5.1 - 如果"listSize"为偶数,则用"listSize/2"初始化中间节点。否则,用 (listSize/2) + 1 初始化 mid。

  • 步骤 5.2 - 如果 root 为 null,则执行 return。

  • 步骤 5.3 - 如果 root 和 end 相等,则用 null 更新 root 和 end 指针。

  • 步骤 5.4 - 如果 mid 等于 1,则用 end 节点更新 root 节点,用 end 更新 end 节点的 next 指针。

  • 步骤 5.5 - 在其他情况下,用 root 节点初始化 'curr',用 null 初始化 'previous',用 1 初始化 p。

  • 步骤 5.6 - 使用循环进行迭代,直到 p 小于 mid。在循环中,用"curr"更新前一个节点,用其下一个节点更新"curr",并将 p 的值加 1。

  • 步骤 5.7 − 之后,用"curr"节点的下一个指针更新"previous"节点的下一个指针。此外,将"curr"设置为 null,并将 listSize 减少 1。

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

  • 步骤 6.1 - 在函数中,使用 do-while 循环遍历列表,并打印每个节点的值。

  • 步骤 7 - 现在,使用 addToList() 方法将节点添加到链接列表。

  • 步骤 8 - 使用 middleDeletion() 函数删除中间元素,并使用 showList() 打印更新列表的元素。

示例

public class Main {
   class dataNode {
      int val;
      dataNode next;
   }
   private static int listSize;
   private dataNode root, end;
   
   // 类构造函数
   Main() {
      this.root = null;
      this.end = null;
      listSize = 0;
   }
   public void addToList(int val) {
   
    // 创建新节点
    dataNode newNode = new dataNode();
    
    // 对于空列表
    if (this.root == null) {
    newNode.val = val;
    this.root = newNode;
    this.end = newNode;
    newNode.next = this.root;
    }
    
    // 在列表的最后附加新节点。将结束节点与根节点连接起来
    else {
    newNode.val = val;
    end.next = newNode;
    end = newNode;
    end.next = root;
    }
    listSize++;
   }
   public void middleDeletion() {
    int mid;
    dataNode curr, previous;
    
    // 中间位置计算
    if (listSize % 2 == 0) {
    mid = listSize / 2;
    } else {
    mid = (listSize / 2) + 1;
    }
    
    // 对于空列表
    if (root == null) {
    return;
    }
    
    // 对于具有单个节点的列表
    else if (root == end) {
    root = null;
    end = null;
    }
    
    // 对于具有两个节点的列表
    else if (mid == 1) {
    root = end;
    end.next = end;
    }
    
    // 对于具有三个或更多节点的列表
    else {
    curr = root;
    previous = null;
    int p = 1;
    
    // 到达中间节点
    while (p < mid) {
    previous = curr;
    curr = curr.next;
    p++;
    }
    
    // 将前一个节点与中间的下一个节点连接起来
    previous.next = curr.next;
    curr = null;
    }
    listSize--;
    if (listSize < 0) {
    listSize = 0;
    }
   }
   public void showList() {
   
    // 对于空列表
    if (root == null) {
    System.out.println("列表为空");
    } else {
    dataNode curr = root;
    
    // 遍历链接列表
    do {
    System.out.print(curr.val + " ");
    curr = curr.next;
    } while (curr != root);
    System.out.println();
    }
   }
   public static void main(String args[]) {
    Main obj = new Main();
    
    // 添加节点
    obj.addToList(90);
    obj.addToList(32);
    obj.addToList(67);
    obj.addToList(84);
    obj.addToList(23);
    obj.addToList(78);
    System.out.print("初始列表为: ");
    obj.showList();
    
    // 删除中间节点
    obj.middleDeletion();
    System.out.print("删除中间节点后更新后的列表为: ");
    obj.showList();
    
    // 删除中间节点
    obj.middleDeletion();
    System.out.print("删除中间节点后更新后的列表为: ");
    obj.showList();
   }
}

输出

初始列表为:90 32 67 84 23 78
删除中间节点后更新的列表为:90 32 84 23 78
删除中间节点后更新的列表为:90 32 23 78
  • 时间复杂度 - O(N) 查找中间元素。

  • 空间复杂度 - O(1),因为我们使用常数空间。

逻辑部分是找到中间节点的前一个和下一个节点,将它们连接起来以删除中间节点。此外,程序员可以练习从循环链表中删除起始或结束节点。


相关文章


有用资源