10. Python 程序：在循环链表的中间插入一个新节点

2025年1月4日 | 阅读 4 分钟

在这个程序中，我们创建一个循环链表，并在列表的中间插入一个新节点。如果列表为空，head 和 tail 都将指向新节点。如果列表不为空，我们将计算列表的大小，并将其除以 2，以获得列表的中间点，新节点需要插入到该中间点。

Python program to insert a new node at the middle of the Circular Linked List

在列表的中间插入新节点后。

考虑上图；新节点需要添加到列表的中间。首先，我们计算大小，在本例中为 4。因此，为了得到中间点，我们将其除以 2 并将其存储在一个名为 count 的变量中。我们将定义两个节点 current 和 temp，以便 temp 指向 head，current 指向 temp 前面的节点。我们遍历列表，直到到达中间点，方法是将 temp 递增到 temp.next，然后在 current 和 temp 之间插入新节点。Current 的 next 节点将是 new，而 new 的 next 节点将是 temp。

算法

定义一个 Node 类，它表示列表中的一个节点。它有两个属性 data 和 next，next 将指向下一个节点。
定义另一个类来创建循环链表，它有两个节点：head 和 tail。变量 size 存储列表的大小。它有两个方法：addInMid() 和 display()。
addInMid() 将节点添加到列表的中间

它首先检查 head 是否为 null（空列表），然后它将节点插入为 head。
head 和 tail 都将指向新添加的节点。
如果列表不为空，那么我们计算大小并将其除以 2 以获得中点。
定义节点 temp，它将指向 head，current 将指向 temp 前面的节点。
通过将 temp 递增到 temp.next 来迭代列表，直到到达列表的中间。
新节点将插入在 current 之后和 temp 之前，使得 current 指向新节点，新节点指向 temp。

a. display() 将显示列表中存在的所有节点。

定义一个新节点“current”，它将指向头节点。
打印 current.data 直到 current 再次指向 head。
在每次迭代中，current 将指向列表中的下一个节点。

程序

#Represents the node of list.  
class Node:  
  def __init__(self,data):  
    self.data = data;  
    self.next = None;  
   
class CreateList:  
    #Declaring head and tail pointer as null.  
    def __init__(self):  
      self.head = Node(None);  
      self.tail = Node(None);  
      self.head.next = self.tail;  
      self.tail.next = self.head;  
      self.size = 0;  
      
    #This function will add the new node to the list.  
    def add(self,data):  
       newNode = Node(data);  
       #Checks if the list is empty.  
       if self.head.data is None:  
         #If list is empty, both head and tail would point to new node.  
         self.head = newNode;  
         self.tail = newNode;  
         newNode.next = self.head;  
       else:  
         #tail will point to new node.  
         self.tail.next = newNode;  
         #New node will become new tail.  
         self.tail = newNode;  
         #Since, it is circular linked list tail will points to head.  
         self.tail.next = self.head;  
       #Size will count the number of element in the list  
       self.size = self.size+1;  
      
    #This function will add the new node at the middle of the list.  
    def addInMid(self,data):  
        newNode = Node(data);  
        #Checks if the list is empty.  
        if(self.head == None):  
            #If list is empty, both head and tail would point to new node.  
            self.head = newNode;  
            self.tail = newNode;  
            newNode.next = self.head;  
        else:  
            #Store the mid-point of the list  
            count = (self.size//2) if (self.size % 2 == 0) else ((self.size+1)//2);  
            #temp will point to head  
            temp = self.head;  
            for i in range(0,count):  
                #Current will point to node previous to temp.  
                current = temp;  
                #Traverse through the list till the middle of the list is reached  
                temp = temp.next;  
            #current will point to new node  
            current.next = newNode;  
            #new node will point to temp  
            newNode.next = temp;  
        self.size = self.size+1;  
          
    #Displays all the nodes in the list  
    def display(self):  
      current = self.head;  
      if self.head is None:  
        print("List is empty");  
        return;  
      else:  
          #Prints each node by incrementing pointer.  
          print(current.data),  
          while(current.next != self.head):  
              current = current.next;  
              print(current.data),  
      
   
class CircularLinkedList:  
    cl = CreateList();  
    #Adds data to the list  
    cl.add(1);  
    cl.add(2);  
    cl.add(3);  
    cl.add(4);  
    print("Original list: ");  
    cl.display();  
    #Inserting node '5' in the middle  
    cl.addInMid(5);  
    print("\nUpdated List: ");  
    cl.display();  
    #Inserting node '6' in the middle  
    cl.addInMid(6);  
    print("\nUpdated List: ");  
    cl.display();  

输出

Original list: 
1 2 3 4
Updated List: 
1 2 5 3 4
Updated List: 
1 2 5 6 3 4

下一个主题Python 程序：对循环链表的元素进行排序

← 上一个下一个 →

10. Python 程序：在循环链表的中间插入一个新节点

算法

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 程序

10. Python 程序：在循环链表的中间插入一个新节点

算法

程序

相关帖子

Python 程序求解二次方程

Python 程序在循环链表开头插入一个新节点

Python 程序查找双向链表中的最大和最小值节点

Python 程序生成随机数

Python 程序右旋数组元素

Python 程序打印数组中奇数位置的元素

Python 函数程序

Python 程序在双向链表中间插入一个新节点

Python 程序：从字符串中删除标点符号

Python 程序查找最小公倍数

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器