算法设计：从未排序的链表中删除重复项

2021年3月10日16:17:41 发表评论 761 次浏览

C ++

``````/* Program to remove duplicates in an unsorted
#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
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

static class Node {

int data;
Node next;

Node( int d) {
data = d;
next = null ;
}
}

/* Function to remove duplicates from an
void remove_duplicates() {
Node ptr1 = null , ptr2 = null , dup = null ;

/* 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) {
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.remove_duplicates();
System.out.println( "" );
System.out.println( "Linked List after removing duplicates : \n " );
}
}
// This code has been contributed by Mayank Jaiswal``````

C#

``````// C# program to remove duplicates from unsorted
using System;
class List_{

class Node{

public
int data;
public
Node next;

public

Node( int d)
{
data = d;
next = null ;
}
}

/* Function to remove duplicates from an
void remove_duplicates()
{
Node ptr1 = null , ptr2 = null , dup = null ;

/* 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_();

Console.WriteLine( "Linked List_ before removing duplicates : \n " );

list.remove_duplicates();
Console.WriteLine( "" );
Console.WriteLine( "Linked List_ after removing duplicates : \n " );
}
}

// This code is contributed by gauravrajput1``````

``````Linked list before removing duplicates:
10 12 11 11 12 11 10
10 12 11``````

1)使用合并排序对元素进行排序。我们很快将写一篇有关对链表进行排序的文章。 O(nLogn)

2)使用

C ++

``````/* Program to remove duplicates in an unsorted
#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
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

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
{
// Hash to store seen values
HashSet<Integer> hs = new HashSet<>();

/* Pick elements one by one */
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 {
prev = current;
}
current = current.next;
}

}

/* Function to print nodes in a given linked list */
{
{
}
}

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``````

C#

``````// C# program to remove duplicates
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
{

// Hash to store seen values
HashSet< int > hs = new HashSet< int >();

// Pick elements one by one
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
{
prev = current;
}
current = current.next;
}
}

// Function to print nodes in a
{
{
}
}

// 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( "\nLinked list after removing " +
"duplicates :" );
printList(start);
}
}

// This code is contributed by amal kumar choubey``````

``````Linked list before removing duplicates:
10 12 11 11 12 11 10