从循环链表中删除重复元素的Java程序

1 简介

在此程序中，我们将创建一个循环链表，并从列表中删除重复的节点。我们将把一个节点与列表的其余部分进行比较，并检查是否重复。如果找到重复的节点，请从列表中删除重复的节点。

1- > 2- > 2- > 4- > 3  

在上面的列表中，我们可以看到，节点2在列表中出现了两次。因此，我们将拥有一个临时节点，该临时节点将遍历列表。索引将指向当前的下一个节点。Temp将指向索引之前的节点。当找到重复项时，我们将temp.next指向index.next来删除它。删除重复项后的上述列表：

1- > 2- > 4- > 3  

2 算法思路

• 定义一个Node类，该类代表列表中的一个节点。它具有两个属性数据，下一个将指向下一个节点。
• 定义另一个用于创建循环链表的类，它具有两个节点：head和tail。
• removeDuplicate（）将从列表中删除重复的节点：
  • 节点当前将指向头部，并用于遍历列表。
  • 索引将指向当前节点的下一个节点，而温度将指向索引的前一个节点。
  • 我们将把current.data与index.data进行比较。如果找到匹配项，则通过将temp指向索引的next来删除重复的数据。
  • 将index递增到index.next，将current递增到current .next。
  • 从c到d重复步骤，直到所有重复项都被删除。

3 程序实现

/**
 * 一点教程网： http://www.yiidian.com
 */
public class RemoveDuplicate {  
//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;  
}  
}  
//Removes duplicate from the list  
public void removeDuplicate() {  
//Current will point to head  
Node current = head, index = null, temp = null;  
if(head == null) {  
System.out.println("List is empty");  
}  
else {  
do{  
//Temp will point to previous node of index.  
temp = current;  
//Index will point to node next to current  
index = current.next;  
while(index != head) {  
//If current node is equal to index data  
if(current.data == index.data) {  
//Here, index node is pointing to the node which is duplicate of current node  
//Skips the duplicate node by pointing to next node  
temp.next = index.next;  
}  
else {  
//Temp will point to previous node of index.  
temp = index;  
}  
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) {  
RemoveDuplicate cl = new RemoveDuplicate();  
//Adds data to the list  
cl.add(1);  
cl.add(2);  
cl.add(3);  
cl.add(2);  
cl.add(2);  
cl.add(4);  
System.out.println("Originals list: ");  
cl.display();  
//Removes duplicate nodes  
cl.removeDuplicate();  
System.out.println("List after removing duplicates: ");  
cl.display();  
}  
} 

输出结果为：

Originals list: 
 1 2 3 2 2 4
List after removing duplicates: 
 1 2 3 4