对循环链表的元素排序的Java程序

1 简介

在此程序中，我们将创建一个循环链表，并按升序对列表进行排序。在此示例中，我们维护两个节点：current将指向head的节点和index将指向current的下一个节点。第一个循环，保持当前状态，第二个循环，保持索引状态。在第一个迭代中，当前将指向9。索引将指向当前旁边的节点（在本例中为5）。将9与5进行比较，因为9> 5，将索引节点的数据与当前节点交换。现在，当前将有5。现在，将5与2进行比较。再次5> 2，交换数据。现在，临时节点将保持2，索引将保持7。2 <7，将不会执行任何操作。索引将增加并指向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

2 算法思路

• 定义一个Node类，该类代表列表中的一个节点。它具有两个属性数据，下一个将指向下一个节点。
• 定义另一个用于创建循环链接列表的类，它具有两个节点：head和tail。
• sortList（）将对列表进行排序：
  • 我们将保持两个当前节点指向头，而索引将指向当前节点旁边。
  • 从索引开始遍历列表，直到到达末尾。
  • 如果current.data大于index.data，请在它们之间交换数据。
  • 在第一次迭代中，我们将在列表的开头获得最小的元素。
  • 然后，当前将指向current.next。
  • 重复步骤b到e，直到获得下一个最小节点。
  • 在两个循环的末尾，将对列表进行排序。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
public class SortList {  
//Represents the node of list.  
public class Node{  
int data;  
Node next;  
public Node(int data) {  
this.data = data;  
}  
}  
//Declaring head and tail pointer as null.  
public Node head = null;  
public Node tail = null;  
//This function will add the new node at the end of the list.  
public void add(int data){  
//Create new node  
Node newNode = new Node(data);  
//Checks if the list is empty.  
if(head == null) {  
 //If list is empty, both head and tail would point to new node.  
head = newNode;  
tail = newNode;  
newNode.next = head;  
}  
else {  
//tail will point to new node.  
tail.next = newNode;  
//New node will become new tail.  
tail = newNode;  
//Since, it is circular linked list tail will points to head.  
tail.next = head;  
}  
}  
//This function sorts the list in ascending order  
public void sortList() {  
//Current will point to head  
Node current = head, index = null;  
int temp;  
if(head == null) {  
System.out.println("List is empty");  
}  
else {  
do{  
//Index will point to node next to current  
index = current.next;  
while(index != 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;  
}while(current.next != head);  
}  
}  
//Displays all the nodes in the list  
public void display() {  
Node current = head;  
if(head == null) {  
System.out.println("List is empty");  
}  
else {  
 do{  
//Prints each node by incrementing pointer.  
System.out.print(" "+ current.data);  
current = current.next;  
}while(current != head);  
System.out.println();  
}  
}  
public static void main(String[] args) {  
SortList cl = new SortList();  
//Adds data to the list  
cl.add(70);  
cl.add(90);  
cl.add(20);  
cl.add(100);  
cl.add(50);  
//Displaying original list  
System.out.println("Original list: ");  
cl.display();  
//Sorting list  
cl.sortList();  
//Displaying sorted list  
System.out.println("Sorted list: ");  
cl.display();  
}}  

输出结果为：

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