Java 从循环链表中删除一个节点

在这个 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 - 定义 ‘dataNode’ 类，包含整型变量 ‘val’ 和 ‘dataNode’ 类型的下一个指针。
步骤 2 - 定义静态变量 ‘listSize’ 来存储链表的大小。同时，定义 ‘root’ 和 ‘end’ 指针来存储第一个和最后一个节点。
步骤 3 - 接下来，定义类的构造函数，将 ‘root’ 和 ‘end’ 节点以及列表的大小初始化为0。
步骤 4 - 定义 addToList() 函数来将节点添加到循环链表中。
步骤 4.1 - 在 addToList() 函数中，使用给定的值定义类型为 ‘dataNode’ 的 ‘newNode’。
步骤 4.2 − 如果根节点为空，则用新节点更新根节点和尾节点。同时，将新节点的下一个指针更新为根节点。
步骤 4.3 − 否则，将最后一个节点的下一个指针指向新节点。同时，更新“end”指针的值，并将最后一个节点的下一个指针更新为“root”节点。
步骤 4.4 − 在添加节点后，将“listSize”增加1。
步骤 5 − 定义middleDeletion()函数来删除中间节点。
步骤 5.1 − 如果“listSize”是偶数，则将“mid”初始化为“listSize/2”。否则，将“mid”初始化为“(listSize/2) + 1”。
步骤 5.2 − 如果根节点为空，则执行返回。
步骤 5.3 − 如果根节点和结束节点相等，则将根节点和结束节点指针更新为 null。
步骤 5.4 − 如果 mid 等于 1，则将根节点更新为结束节点，并将结束节点的下一个指针更新为结束点。
步骤 5.5 − 在其他情况下，将 ‘curr’ 初始化为根节点，’previous’ 初始化为 null，p 初始化为 1。
步骤 5.6 − 使用循环迭代直到 p 小于 mid。在循环中，将 previous 更新为 ‘curr’，’curr’ 更新为其下一个节点，并将 p 的值增加 1。
步骤 5.7
- − 在此之后，将“previous”节点的下一个指针更新为“curr”节点的下一个指针。同时，将“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;

   // Class constructor
   Main() {
      this.root = null;
      this.end = null;
      listSize = 0;
   }
   public void addToList(int val) {

      // New node creation
      dataNode newNode = new dataNode();

      // For empty list
      if (this.root == null) {
         newNode.val = val;
         this.root = newNode;
         this.end = newNode;
         newNode.next = this.root;
      }

      // Append new node at last of the list. connect end node with the root node
      else {
         newNode.val = val;
         end.next = newNode;
         end = newNode;
         end.next = root;
      }
      listSize++;
   }
   public void middleDeletion() {
      int mid;
      dataNode curr, previous;

      // Middle position calculation
      if (listSize % 2 == 0) {
         mid = listSize / 2;
      } else {
         mid = (listSize / 2) + 1;
      }

      // For an empty list
      if (root == null) {
         return;
      }

      // For a list having a single node
      else if (root == end) {
         root = null;
         end = null;
      }

      // For list having two nodes
      else if (mid == 1) {
         root = end;
         end.next = end;
      }

      // For a list having three or more nodes
      else {
         curr = root;
         previous = null;
         int p = 1;

         // Reach to the middle node
         while (p < mid) {
            previous = curr;
            curr = curr.next;
            p++;
         }

         // Join the previous node with next node of middle
         previous.next = curr.next;
         curr = null;
      }
      listSize--;
      if (listSize < 0) {
         listSize = 0;
      }
   }
   public void showList() {

      // For an empty list
      if (root == null) {
         System.out.println("The list is empty");
      } else {
         dataNode curr = root;

         // Traverse the linked list
         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();

      // Add nodes
      obj.addToList(90);
      obj.addToList(32);
      obj.addToList(67);
      obj.addToList(84);
      obj.addToList(23);
      obj.addToList(78);
      System.out.print("Initial list is: ");
      obj.showList();

      // Middle node deletion
      obj.middleDeletion();
      System.out.print("The updated list after deleting the middle node is: ");
      obj.showList();

      // Middle node deletion
      obj.middleDeletion();
      System.out.print("The updated list after deleting the middle node is: ");
      obj.showList();
   }
}

输出

Initial list is: 90 32 67 84 23 78 
The updated list after deleting the middle node is: 90 32 84 23 78 
The updated list after deleting the middle node is: 90 32 23 78