13. Python 程序，用于对循环链表的元素进行排序

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

在这个程序中，我们将创建一个循环链表，并按升序对列表进行排序。在这个例子中，我们维护两个节点：current 指向头部，index 指向 current 的下一个节点。第一个循环跟踪 current，第二个循环跟踪 index。在第一次迭代中，current 将指向 9。index 将指向 current 之后的节点，在本例中为 5。 9 与 5 进行比较，因为 9 > 5，交换 index 节点与 current 节点的数据。现在，current 将有 5。现在，5 将与 2 进行比较。同样 5 > 2，交换数据。现在 current 将保持 2，index 将保持 7。2 < 7，什么都不做。index 将递增并指向 3. 2 < 3。什么都不做。这样，我们将在第一个位置得到一个最小值节点。然后，我们将继续在列表的其余部分中查找最小元素，直到列表完全排序。

9->5->2->7->3
2->9->5->7->3
2->3->9->7->5
2->3->5->9->7
2->3->5->7->9

算法

定义一个 Node 类，它表示列表中的一个节点。它有两个属性 data 和 next，next 将指向下一个节点。
定义另一个类来创建循环链表，它有两个节点：head 和 tail。
sortList() 将对列表进行排序

我们将维护两个节点：current 指向 head，index 指向 current 的下一个节点。
从 index 开始遍历列表，直到到达末尾。
如果 current.data 大于 index.data，则交换它们之间的数据。
在第一次迭代中，我们将在列表的开头得到最小的元素。
然后 current 将指向 current.next。
重复步骤 b 到 e，直到找到下一个最小节点。
两个循环结束后，列表将被排序。

程序

#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;  
      
    #This function will add the new node at the end of 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 point to head.  
            self.tail.next = self.head;  
      
    #This function sorts the list in ascending order  
    def sortList(self):  
        #Current will point to head  
        current = self.head;  
        if(self.head == None):  
            print("List is empty");  
        else:  
            while(True):  
                #Index will point to node next to current  
                index = current.next;  
                while(index != self.head):  
                    #If current node is greater than index data, swaps the data  
                    if(current.data > index.data):  
                        temp = current.data;  
                        current.data = index.data;  
                        index.data = temp;  
                    index= index.next;  
                current =current.next;  
                if(current.next == self.head):  
                    break;  
                      
    #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, end= ' ');  
            while(current.next != self.head):  
                current = current.next;  
                print(current.data,end=' ');  
        print("\n");  
              
class CircularLinkedList:  
    cl = CreateList();  
    #Adds data to the list  
    cl.add(70);  
    cl.add(90);  
    cl.add(20);  
    cl.add(100);  
    cl.add(50);  
      
    #Displaying original list  
    print("Original list: ");  
    cl.display();  
      
    #Sorting list  
    cl.sortList();  
      
    #Displaying sorted list  
    print("Sorted list: ");  
    cl.display();  

输出

Original list: 
70 90 20 100 50
Sorted list: 
20 50 70 90 100

下一个主题Python 函数程序

← 上一个下一个 →

13. 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 程序

13. Python 程序，用于对循环链表的元素进行排序

算法

程序

相关帖子

Python 中的阿姆斯特朗数

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

Python 程序按降序对数组元素进行排序

Python 程序将摄氏度转换为华氏度

Python 程序检查数字是正数、负数还是零

Python 程序制作一个简单的计算器

Python 程序在双向链表开头插入一个新节点

Python 程序查找最小公倍数

Python 程序

Python 程序：两个矩阵相乘

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器