算法（如何从排序的链表中删除所有重复项（））

本文概述

C ++
Java
Python3
C#

给定一个已排序的链表, 请删除所有具有重复编号(所有出现次数)的节点, 仅保留在原始列表中仅出现一次的编号。
例子：

Input : 23-> 28-> 28-> 35-> 49-> 49-> 53-> 53 Output : 23-> 35Input : 11-> 11-> 11-> 11-> 75-> 75 Output : empty List

请注意, 这与从链表中删除重复项
这个想法是维护一个指针(上一个)到恰好在节点块之前的节点, 我们正在检查重复项。在第一个示例中, 指针上一个在检查节点28的重复项时将指向23。一旦到达最后一个值为28的重复节点(将其命名为当前指针), 我们可以使上一个节点的下一个字段成为当前节点的下一个并更新当前= current.next。这将删除具有重复项的值为28的节点块。
C ++

// C++ program to remove all // occurrences of duplicates // from a sorted 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 = https://www.lsbin.com/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 // head of list pointing // to the original head Node* dummy = new Node; // dummy node points // to the original head dummy -> next = start; // Node pointing to last // node which has no duplicate. Node* prev = dummy; // Node used to traverse // the linked list. Node* current = start; while (current != NULL) { // Until the current and // previous values are // same, keep updating current while (current -> next != NULL & & prev -> next -> data =https://www.lsbin.com/= 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; }// update original head to // 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 LinkedList{// head of linked list Node head = null ; 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); new_node.next = head; head = new_node; }// Function to remove all occurrences // of duplicate elements public void removeAllDuplicates() {// Create a dummy node that acts like a fake // head of list pointing to the original head Node dummy = new Node( 0 ); // Dummy node points to the original head dummy.next = head; Node prev = dummy; Node current = head; 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 head = dummy.next; }// Function to print the list elements public void printList() { Node trav = head; if (head == null ) 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) { LinkedList ll = new LinkedList(); 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 class LinkedList: def __init__( self ): self .head = None# add node into beganing of linked list def push( self , new_data): new_node = Node(new_data) new_node. next = self .head self .head = new_node return new_node# Function to remove all occurrences # of duplicate elements def removeAllDuplicates( self , temp):# temp is head node of linkedlist curr = temp # print(' print something') head = prev = Node( None ) head. next = curr# 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 return head. next# for print the linkedlist def printList( self ): temp1 = self .head while temp1 is not None : print (temp1.val, end = " " ) temp1 = temp1. next# For getting head of linkedlist def get_head( self ): return self .head# Driver Code if __name__ = = '__main__' : llist = LinkedList() 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:' ) head1 = llist.get_head() #print(head1) llist.removeAllDuplicates(head1) llist.printList()# This code is contributed # by PRAVEEN KUMAR(IIIT KALYANI)

/* C# program to remove all occurrences of duplicates from a sorted linked list */using System; /* class to create Linked lIst */ public class LinkedList { Node head = null ; /* head of 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); new_node.next = head; head = new_node; }/* Function to remove all occurrences of duplicate elements */ public void removeAllDuplicates() { /* create a dummy node that acts like a fake head of list pointing to the original head*/ Node dummy = new Node(0); /* dummy node points to the original head*/ dummy.next = head; Node prev = dummy; Node current = head; 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 */ head = dummy.next; }/* Function to print the list elements */ public void printList() { Node trav = head; if (head == null ) Console.Write( " List is empty" ); while (trav != null ) { Console.Write(trav.val + " " ); trav = trav.next; } }/* Driver code */ public static void Main(String[] args) { LinkedList ll = new LinkedList(); 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

输出如下：