编写RemovedUpplicates（）函数，该函数获取列表并从列表中删除任何重复节点。列表未排序。 例如，如果链接列表是12->11->12->21->41->43->21，那么RemovedUpplicates（）应该将列表转换为12->11->21->41->43。
null
方法1（使用两个循环） 这是使用两个循环的简单方法。外循环用于逐个拾取元素，内循环将拾取的元素与其余元素进行比较。 感谢Gaurav Saxena在编写这段代码时的帮助。
C++
/* C++ Program to remove duplicates in an unsorted linked list */ #include <bits/stdc++.h> using namespace std; /* A linked list node */ struct Node { int data; struct Node* next; }; // Utility function to create a new Node struct Node* newNode( int data) { Node* temp = new Node; temp->data = data; temp->next = NULL; return temp; } /* Function to remove duplicates from a unsorted linked list */ void removeDuplicates( struct Node* start) { struct Node *ptr1, *ptr2, *dup; ptr1 = start; /* Pick elements one by one */ while (ptr1 != NULL && ptr1->next != NULL) { ptr2 = ptr1; /* Compare the picked element with rest of the elements */ while (ptr2->next != NULL) { /* If duplicate then delete it */ if (ptr1->data == ptr2->next->data) { /* sequence of steps is important here */ dup = ptr2->next; ptr2->next = ptr2->next->next; delete (dup); } else /* This is tricky */ ptr2 = ptr2->next; } ptr1 = ptr1->next; } } /* Function to print nodes in a given linked list */ void printList( struct Node* node) { while (node != NULL) { printf ( "%d " , node->data); node = node->next; } } /* Driver program to test above function */ int main() { /* The constructed linked list is: 10->12->11->11->12->11->10*/ struct Node* start = newNode(10); start->next = newNode(12); start->next->next = newNode(11); start->next->next->next = newNode(11); start->next->next->next->next = newNode(12); start->next->next->next->next->next = newNode(11); start->next->next->next->next->next->next = newNode(10); printf ( "Linked list before removing duplicates " ); printList(start); removeDuplicates(start); printf ( "Linked list after removing duplicates " ); printList(start); return 0; } |
JAVA
// Java program to remove duplicates from unsorted // linked list class LinkedList { static Node head; static class Node { int data; Node next; Node( int d) { data = d; next = null ; } } /* Function to remove duplicates from an unsorted linked list */ void remove_duplicates() { Node ptr1 = null , ptr2 = null , dup = null ; ptr1 = head; /* Pick elements one by one */ while (ptr1 != null && ptr1.next != null ) { ptr2 = ptr1; /* Compare the picked element with rest of the elements */ while (ptr2.next != null ) { /* If duplicate then delete it */ if (ptr1.data == ptr2.next.data) { /* sequence of steps is important here */ ptr2.next = ptr2.next.next; System.gc(); } else /* This is tricky */ { ptr2 = ptr2.next; } } ptr1 = ptr1.next; } } void printList(Node node) { while (node != null ) { System.out.print(node.data + " " ); node = node.next; } } public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node( 10 ); list.head.next = new Node( 12 ); list.head.next.next = new Node( 11 ); list.head.next.next.next = new Node( 11 ); list.head.next.next.next.next = new Node( 12 ); list.head.next.next.next.next.next = new Node( 11 ); list.head.next.next.next.next.next.next = new Node( 10 ); System.out.println( "Linked List before removing duplicates : " ); list.printList(head); list.remove_duplicates(); System.out.println( "" ); System.out.println( "Linked List after removing duplicates : " ); list.printList(head); } } // This code has been contributed by Mayank Jaiswal |
蟒蛇3
# Python3 program to remove duplicates # from unsorted linked list class Node(): def __init__( self , data): self .data = data self . next = None class LinkedList(): def __init__( self ): # Head of list self .head = None def remove_duplicates( self ): ptr1 = None ptr2 = None dup = None ptr1 = self .head # Pick elements one by one while (ptr1 ! = None and ptr1. next ! = None ): ptr2 = ptr1 # Compare the picked element with rest # of the elements while (ptr2. next ! = None ): # If duplicate then delete it if (ptr1.data = = ptr2. next .data): # Sequence of steps is important here dup = ptr2. next ptr2. next = ptr2. next . next else : ptr2 = ptr2. next ptr1 = ptr1. next # Function to print nodes in a # given linked list def printList( self ): temp = self .head while (temp ! = None ): print (temp.data, end = " " ) temp = temp. next print () # Driver code list = LinkedList() list .head = Node( 10 ) list .head. next = Node( 12 ) list .head. next . next = Node( 11 ) list .head. next . next . next = Node( 11 ) list .head. next . next . next . next = Node( 12 ) list .head. next . next . next . next . next = Node( 11 ) list .head. next . next . next . next . next . next = Node( 10 ) print ( "Linked List before removing duplicates :" ) list .printList() list .remove_duplicates() print () print ( "Linked List after removing duplicates :" ) list .printList() # This code is contributed by maheshwaripiyush9 |
C#
// C# program to remove duplicates from unsorted // linked list using System; class List_ { Node head; class Node { public int data; public Node next; public Node( int d) { data = d; next = null ; } } /* Function to remove duplicates from an unsorted linked list */ void remove_duplicates() { Node ptr1 = null , ptr2 = null , dup = null ; ptr1 = head; /* Pick elements one by one */ while (ptr1 != null && ptr1.next != null ) { ptr2 = ptr1; /* Compare the picked element with rest of the elements */ while (ptr2.next != null ) { /* If duplicate then delete it */ if (ptr1.data == ptr2.next.data) { /* sequence of steps is important here */ dup = ptr2.next; ptr2.next = ptr2.next.next; } else /* This is tricky */ { ptr2 = ptr2.next; } } ptr1 = ptr1.next; } } void printList(Node node) { while (node != null ) { Console.Write(node.data + " " ); node = node.next; } } // Driver Code public static void Main(String[] args) { List_ list = new List_(); list.head = new Node(10); list.head.next = new Node(12); list.head.next.next = new Node(11); list.head.next.next.next = new Node(11); list.head.next.next.next.next = new Node(12); list.head.next.next.next.next.next = new Node(11); list.head.next.next.next.next.next.next = new Node(10); Console.WriteLine( "Linked List_ before removing duplicates : " ); list.printList(list.head); list.remove_duplicates(); Console.WriteLine( "" ); Console.WriteLine( "Linked List_ after removing duplicates : " ); list.printList(list.head); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // javascript program to remove duplicates from unsorted // linked list var head; class Node { constructor(val) { this .data = val; this .next = null ; } } /* * Function to remove duplicates from an unsorted linked list */ function remove_duplicates() { var ptr1 = null , ptr2 = null , dup = null ; ptr1 = head; /* Pick elements one by one */ while (ptr1 != null && ptr1.next != null ) { ptr2 = ptr1; /* * Compare the picked element with rest of the elements */ while (ptr2.next != null ) { /* If duplicate then delete it */ if (ptr1.data == ptr2.next.data) { /* sequence of steps is important here */ dup = ptr2.next; ptr2.next = ptr2.next.next; } else /* This is tricky */ { ptr2 = ptr2.next; } } ptr1 = ptr1.next; } } function printList( node) { while (node != null ) { document.write(node.data + " " ); node = node.next; } } head = new Node(10); head.next = new Node(12); head.next.next = new Node(11); head.next.next.next = new Node(11); head.next.next.next.next = new Node(12); head.next.next.next.next.next = new Node(11); head.next.next.next.next.next.next = new Node(10); document.write( "Linked List before removing duplicates : <br/> " ); printList(head); remove_duplicates(); document.write( "<br/>" ); document.write( "Linked List after removing duplicates : <br/> " ); printList(head); // This code contributed by aashish1995 </script> |
输出
Linked list before removing duplicates 10 12 11 11 12 11 10 Linked list after removing duplicates 10 12 11
时间复杂度：O（n^2）
方法2（使用排序） 一般来说，合并排序是最适合高效排序链表的排序算法。 1） 使用合并排序对元素进行排序。我们很快就会写一篇关于链表排序的帖子。O（nLogn） 2） 使用 移除排序链表中重复项的算法。O（n） 请注意，此方法不会保留元素的原始顺序。 时间复杂度：O（nLogn）
方法3（使用哈希） 我们从头到尾遍历链接列表。对于每个新遇到的元素，我们检查它是否在哈希表中：如果是，我们将其删除；否则我们就把它放到哈希表中。
C++
/* C++ Program to remove duplicates in an unsorted linked list */ #include <bits/stdc++.h> using namespace std; /* A linked list node */ struct Node { int data; struct Node* next; }; // Utility function to create a new Node struct Node* newNode( int data) { Node* temp = new Node; temp->data = data; temp->next = NULL; return temp; } /* Function to remove duplicates from a unsorted linked list */ void removeDuplicates( struct Node* start) { // Hash to store seen values unordered_set< int > seen; /* Pick elements one by one */ struct Node* curr = start; struct Node* prev = NULL; while (curr != NULL) { // If current value is seen before if (seen.find(curr->data) != seen.end()) { prev->next = curr->next; delete (curr); } else { seen.insert(curr->data); prev = curr; } curr = prev->next; } } /* Function to print nodes in a given linked list */ void printList( struct Node* node) { while (node != NULL) { printf ( "%d " , node->data); node = node->next; } } /* Driver program to test above function */ int main() { /* The constructed linked list is: 10->12->11->11->12->11->10*/ struct Node* start = newNode(10); start->next = newNode(12); start->next->next = newNode(11); start->next->next->next = newNode(11); start->next->next->next->next = newNode(12); start->next->next->next->next->next = newNode(11); start->next->next->next->next->next->next = newNode(10); printf ( "Linked list before removing duplicates : " ); printList(start); removeDuplicates(start); printf ( "Linked list after removing duplicates : " ); printList(start); return 0; } |
JAVA
// Java program to remove duplicates // from unsorted linkedlist import java.util.HashSet; public class removeDuplicates { static class node { int val; node next; public node( int val) { this .val = val; } } /* Function to remove duplicates from a unsorted linked list */ static void removeDuplicate(node head) { // Hash to store seen values HashSet<Integer> hs = new HashSet<>(); /* Pick elements one by one */ node current = head; node prev = null ; while (current != null ) { int curval = current.val; // If current value is seen before if (hs.contains(curval)) { prev.next = current.next; } else { hs.add(curval); prev = current; } current = current.next; } } /* Function to print nodes in a given linked list */ static void printList(node head) { while (head != null ) { System.out.print(head.val + " " ); head = head.next; } } public static void main(String[] args) { /* The constructed linked list is: 10->12->11->11->12->11->10*/ node start = new node( 10 ); start.next = new node( 12 ); start.next.next = new node( 11 ); start.next.next.next = new node( 11 ); start.next.next.next.next = new node( 12 ); start.next.next.next.next.next = new node( 11 ); start.next.next.next.next.next.next = new node( 10 ); System.out.println( "Linked list before removing duplicates :" ); printList(start); removeDuplicate(start); System.out.println( "Linked list after removing duplicates :" ); printList(start); } } // This code is contributed by Rishabh Mahrsee |
蟒蛇3
# Python3 program to remove duplicates # from unsorted linkedlist class Node: def __init__( self , data): self .data = data self . next = None class LinkedList: def __init__( self ): self .head = None # Function to print nodes in a # given linked list def printlist( self ): temp = self .head while (temp): print (temp.data, end = " " ) temp = temp. next # Function to remove duplicates from a # unsorted linked list def removeDuplicates( self , head): # Base case of empty list or # list with only one element if self .head is None or self .head. next is None : return head # Hash to store seen values hash = set () current = head hash .add( self .head.data) while current. next is not None : if current. next .data in hash : current. next = current. next . next else : hash .add(current. next .data) current = current. next return head # Driver code if __name__ = = "__main__" : # Creating Empty list llist = LinkedList() llist.head = Node( 10 ) second = Node( 12 ) third = Node( 11 ) fourth = Node( 11 ) fifth = Node( 12 ) sixth = Node( 11 ) seventh = Node( 10 ) # Connecting second and third llist.head. next = second second. next = third third. next = fourth fourth. next = fifth fifth. next = sixth sixth. next = seventh # Printing data print ( "Linked List before removing Duplicates." ) llist.printlist() llist.removeDuplicates(llist.head) print ( "Linked List after removing duplicates." ) llist.printlist() # This code is contributed by rajataro0 |
C#
// C# program to remove duplicates // from unsorted linkedlist using System; using System.Collections.Generic; class removeDuplicates { class node { public int val; public node next; public node( int val) { this .val = val; } } // Function to remove duplicates from a // unsorted linked list static void removeDuplicate(node head) { // Hash to store seen values HashSet< int > hs = new HashSet< int >(); // Pick elements one by one node current = head; node prev = null ; while (current != null ) { int curval = current.val; // If current value is seen before if (hs.Contains(curval)) { prev.next = current.next; } else { hs.Add(curval); prev = current; } current = current.next; } } // Function to print nodes in a // given linked list static void printList(node head) { while (head != null ) { Console.Write(head.val + " " ); head = head.next; } } // Driver code public static void Main(String[] args) { // The constructed linked list is: // 10->12->11->11->12->11->10 node start = new node(10); start.next = new node(12); start.next.next = new node(11); start.next.next.next = new node(11); start.next.next.next.next = new node(12); start.next.next.next.next.next = new node(11); start.next.next.next.next.next.next = new node(10); Console.WriteLine( "Linked list before removing " + "duplicates :" ); printList(start); removeDuplicate(start); Console.WriteLine( "Linked list after removing " + "duplicates :" ); printList(start); } } // This code is contributed by amal kumar choubey |
Javascript
<script> // JavaScript program to remove duplicates // from unsorted linkedlist class node { constructor(val) { this .val = val; this .next = null ; } } /* Function to remove duplicates from a unsorted linked list */ function removeDuplicate( head) { // Hash to store seen values var hs = new Set(); /* Pick elements one by one */ var current = head; var prev = null ; while (current != null ) { var curval = current.val; // If current value is seen before if (hs.has(curval)) { prev.next = current.next; } else { hs.add(curval); prev = current; } current = current.next; } } /* Function to print nodes in a given linked list */ function printList( head) { while (head != null ) { document.write(head.val + " " ); head = head.next; } } /* * The constructed linked list is: 10->12->11->11->12->11->10 */ start = new node(10); start.next = new node(12); start.next.next = new node(11); start.next.next.next = new node(11); start.next.next.next.next = new node(12); start.next.next.next.next.next = new node(11); start.next.next.next.next.next.next = new node(10); document.write( "Linked list before removing duplicates :<br/>" ); printList(start); removeDuplicate(start); document.write( "<br/>Linked list after removing duplicates :<br/>" ); printList(start); // This code is contributed by todaysgaurav </script> |
输出
Linked list before removing duplicates : 10 12 11 11 12 11 10 Linked list after removing duplicates : 10 12 11
感谢bearwang提出的这种方法。 时间复杂度：平均为O（n）（假设哈希表访问时间平均为O（1））。
–oI4 如果您发现上述任何解释/算法不正确，或发现解决同一问题的更好方法，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
