编写一个removeduplicates（）函数，该函数获取一个列表并从列表中删除所有重复的节点。列表未排序。
例如，如果链表是12->11->12->21->41->43->21，那么removeUplicates（）应该将链表转换为12->11->21->41->43。
建议：请先在“实践”中解决，然后再继续解决问题。
方法1（使用两个回路）
这是使用两个循环的简单方法。外循环用于逐个选取元素，内循环将选取的元素与其余元素进行比较。
感谢Gaurav Saxena在编写此代码方面的帮助。
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;
}
}
/* Druver 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("\nLinked 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 */
dup = ptr2.next;
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 : \n ");
list.printList(head);
list.remove_duplicates();
System.out.println("");
System.out.println("Linked List after removing duplicates : \n ");
list.printList(head);
}
}
// This code has been contributed by Mayank Jaiswal
|
Output :
Linked list before removing duplicates:
10 12 11 11 12 11 10
Linked list after removing duplicates:
10 12 11
|
时间复杂度: O(n^2)
方法2（使用排序）
通常，Merge Sort是最适合用于有效排序链表的排序算法。
1）使用Merge Sort对元素进行排序。 我们很快就会写一篇关于排序链表的帖子。O(nLogn）
2）使用用于删除已排序的链接列表中的重复项的算法，以线性时间删除重复项。O(n)
请注意，此方法不保留元素的原始顺序。
时间复杂度：O(nLogn)
方法3（使用哈希）
我们从头到尾遍历链接列表。 对于每个新遇到的元素，我们检查它是否在哈希表中：如果是，我们将其删除; 否则我们把它放在哈希表中。
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 : \n");
printList(start);
removeDuplicates(start);
printf("\nLinked list after removing duplicates : \n");
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("\nLinked list after removing duplicates :");
printList(start);
}
}
// This code is contributed by Rishabh Mahrsee
|
Output :
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)）。