# 算法：如何从排序的链表中删除所有重复项？

2021年3月27日17:34:18 发表评论 852 次浏览

## 本文概述

``````Input : 23->28->28->35->49->49->53->53
Output : 23->35

Input : 11->11->11->11->75->75
Output : empty List``````

## C ++

``````// C++ program to remove all
// occurrences of duplicates
// from a sorted linked list.
#include <bits/stdc++.h>
using namespace std;

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 print nodes
// in a given linked list.
void printList( struct Node *node)
{
while (node != NULL)
{
printf ( "%d " , node -> data);
node = node -> next;
}
}

// Function to remove all occurrences
// of duplicate elements
void removeAllDuplicates( struct Node* &start)
{
// create a dummy node
// that acts like a fake
Node* dummy = new Node;

// dummy node points
dummy -> next = start;

// Node pointing to last
// node which has no duplicate.
Node* prev = dummy;

// Node used to traverse
Node* current = start;

while (current != NULL)
{
// Until the current and
// previous values are
// same, keep updating current
while (current -> next != NULL &&
prev -> next -> data == current -> next -> data)
current = current -> next;

// if current has unique value
// i.e current is not updated, // Move the prev pointer to
// next node
if (prev -> next == current)
prev = prev -> next;

// when current is updated
// to the last duplicate
// value of that segment, // make prev the next of current
else
prev -> next = current -> next;

current = current -> next;
}

// the next of dummy node
start = dummy -> next;
}

// Driver Code
int main()
{
// 23->28->28->35->49->49->53->53
struct Node* start = newNode(23);
start -> next = newNode(28);
start -> next -> next = newNode(28);
start -> next ->
next -> next = newNode(35);
start -> next ->
next -> next -> next = newNode(49);
start -> next ->
next -> next ->
next -> next = newNode(49);
start -> next ->
next -> next ->
next -> next -> next = newNode(53);
start -> next ->
next -> next ->
next -> next ->
next -> next = newNode(53);
cout << "List before removal " <<
"of duplicates\n" ;
printList(start);

removeAllDuplicates(start);

cout << "\nList after removal " <<
"of duplicates\n" ;
printList(start);
return 0;
}

// This code is contributed
// by NIKHIL JINDAL``````

## Java

``````// Java program to remove all occurrences of
// duplicates from a sorted linked list

// class to create Linked lIst

class Node
{

// value in the node
int val;
Node next;
Node( int v)
{

// default value of the next
// pointer field
val = v;
next = null ;
}
}

// Function to insert data nodes into
// the Linked List at the front
public void insert( int data)
{
Node new_node = new Node(data);
}

// Function to remove all occurrences
// of duplicate elements
public void removeAllDuplicates()
{

// Create a dummy node that acts like a fake
Node dummy = new Node( 0 );

// Dummy node points to the original head
Node prev = dummy;

while (current != null )
{
// Until the current and previous values
// are same, keep updating current
while (current.next != null &&
prev.next.val == current.next.val)
current = current.next;

// If current has unique value i.e current
// is not updated, Move the prev pointer
// to next node
if (prev.next == current)
prev = prev.next;

// When current is updated to the last
// duplicate value of that segment, make
// prev the next of current*/
else
prev.next = current.next;

current = current.next;
}

// Update original head to the next of dummy
// node
}

// Function to print the list elements
public void printList()
{
System.out.print( " List is empty" );

while (trav != null )
{
System.out.print(trav.val + " " );
trav = trav.next;
}
}

// Driver code
public static void main(String[] args)
{
ll.insert( 53 );
ll.insert( 53 );
ll.insert( 49 );
ll.insert( 49 );
ll.insert( 35 );
ll.insert( 28 );
ll.insert( 28 );
ll.insert( 23 );

System.out.println( "Before removal of duplicates" );
ll.printList();

ll.removeAllDuplicates();

System.out.println( "\nAfter removal of duplicates" );
ll.printList();
}
}``````

## Python3

``````# Python3 implementation for the above approach

# Creating node
class Node:
def __init__( self , val):
self .val = val
self . next = None
def __init__( self ):

def push( self , new_data):
new_node = Node(new_data)
return new_node

# Function to remove all occurrences
# of duplicate elements
def removeAllDuplicates( self , temp):

curr = temp
# print(' print something')
head = prev = Node( None )

# Here we use same as we do in removing
# duplicates and only extra thing is that
# we need to remove all elements
# having duplicates that we did in 30-31
while curr and curr. next :

# until the current value and next
# value are same keep updating the current value
if curr.val = = curr. next .val:
while (curr and curr. next and
curr.val = = curr. next .val):
curr = curr. next

# still one of duplicate values left
# so point prec to curr
curr = curr. next
prev. next = curr
else :
prev = prev. next
curr = curr. next

def printList( self ):
while temp1 is not None :
print (temp1.val, end = " " )
temp1 = temp1. next

# Driver Code
if __name__ = = '__main__' :
llist.push( 53 )
llist.push( 53 )
llist.push( 49 )
llist.push( 49 )
llist.push( 35 )
llist.push( 28 )
llist.push( 28 )
llist.push( 23 )

print ( 'Created linked list is:' )
llist.printList()
print ( '\nLinked list after deletion of duplicates:' )
llist.printList()

# This code is contributed
# by PRAVEEN KUMAR(IIIT KALYANI)``````

## C#

``````/* C# program to remove all occurrences of
duplicates from a sorted linked list */

using System;

/* class to create Linked lIst */
{
class Node
{
public int val; /* value in the node */
public Node next;
public Node( int v)
{
/* default value of the next
pointer field */
val = v;
next = null ;
}
}

/* Function to insert data nodes into
the Linked List at the front */
public void insert( int data)
{
Node new_node = new Node(data);
}

/* Function to remove all occurrences
of duplicate elements */
public void removeAllDuplicates()
{
/* create a dummy node that acts like a fake
Node dummy = new Node(0);

/* dummy node points to the original head*/
Node prev = dummy;

while (current != null )
{
/* Until the current and previous values
are same, keep updating current */
while (current.next != null &&
prev.next.val == current.next.val)
current = current.next;

/* if current has unique value i.e current
is not updated, Move the prev pointer
to next node*/
if (prev.next == current)
prev = prev.next;

/* when current is updated to the last
duplicate value of that segment, make
prev the next of current*/
else
prev.next = current.next;

current = current.next;
}

/* update original head to the next of dummy
node */
}

/* Function to print the list elements */
public void printList()
{
Console.Write( " List is empty" );
while (trav != null )
{
Console.Write(trav.val + " " );
trav = trav.next;
}
}

/* Driver code */
public static void Main(String[] args)
{
ll.insert(53);
ll.insert(53);
ll.insert(49);
ll.insert(49);
ll.insert(35);
ll.insert(28);
ll.insert(28);
ll.insert(23);
Console.WriteLine( "Before removal of duplicates" );
ll.printList();

ll.removeAllDuplicates();

Console.WriteLine( "\nAfter removal of duplicates" );
ll.printList();
}
}

// This code is contributed by Rajput-Ji``````

``````List before removal of duplicates
23 28 28 35 49 49 53 53
List after removal of duplicates
23 35``````