从已排序的链表中删除所有重复项-yiteyi-C++库

给定一个已排序的链表，删除所有具有重复编号（所有出现）的节点，只保留在原始列表中出现一次的编号。 例如：

null

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

请注意，这与从链表中删除重复项

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

这样做的目的是维护一个指针 （上） 对于节点块前面的节点，我们正在检查重复项。在第一个示例中，指针上当我们检查节点28的重复项时，将指向23。一旦我们到达最后一个值为28的重复节点（命名它） 现在的 指针），我们可以使prev节点的下一个字段成为当前和更新的下一个字段 电流=电流。下一个 。这将删除值为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 = 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 == 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"                                     ;                       
                                                 printList(start);                       
                                   
                                                 removeAllDuplicates(start);                       
                                   
                                                 cout <<                                     "List after removal "                                     <<                       
                                                 "of duplicates"                                     ;                       
                                                 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(                                     "After 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                                     (                                     'Linked 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#

                         /* 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(                                     "After removal of duplicates"                                     );                       
                                                 ll.printList();                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Rajput-Ji                       

Javascript

                         <script>                       
           
                         // Javascript program to remove                       
                         // all occurrences of                       
                         // duplicates from a sorted linked list                       
           
                         // class to create Linked lIst                       
           
           
                                                 // head of linked list                       
                                                 var                                     head =                                     null                                     ;                       
           
                                                 class Node {                       
           
                                                 constructor(val) {                       
                                                 // default value of the next                       
                                                 // pointer field                       
                                                 this                                     .val = val;                       
                                                 this                                     .next =                                     null                                     ;                       
                                                 }                       
                                   
                                                 }                       
           
                                                 // Function to insert data nodes into                       
                                                 // the Linked List at the front                       
                                                 function                                     insert(data) {                       
                         var                                     new_node =                                     new                                     Node(data);                       
                                                 new_node.next = head;                       
                                                 head = new_node;                       
                                                 }                       
           
                                                 // Function to remove all occurrences                       
                                                 // of duplicate elements                       
                                                 function                                     removeAllDuplicates() {                       
           
                                                 // Create a dummy node that acts like a fake                       
                                                 // head of list pointing to the original head                       
                         var                                     dummy =                                     new                                     Node(0);                       
           
                                                 // Dummy node points to the original head                       
                                                 dummy.next = head;                       
                         var                                     prev = dummy;                       
                         var                                     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                       
                                                 function                                     printList() {                       
                         var                                     trav = head;                       
                                                 if                                     (head ==                                     null                                     )                       
                                                 document.write(                                     " List is empty"                                     );                       
           
                                                 while                                     (trav !=                                     null                                     ) {                       
                                                 document.write(trav.val +                                     " "                                     );                       
                                                 trav = trav.next;                       
                                                 }                       
                                                 }                       
           
                                                 // Driver code                       
                                   
                                                 insert(53);                       
                                                 insert(53);                       
                                                 insert(49);                       
                                                 insert(49);                       
                                                 insert(35);                       
                                                 insert(28);                       
                                                 insert(28);                       
                                                 insert(23);                       
           
                                                 document.write(                       
                                                 "Before removal of duplicates<br/>"                       
                                                 );                       
                                                 printList();                       
           
                                                 removeAllDuplicates();                       
           
                                                 document.write(                       
                                                 "<br/>After removal of duplicates<br/>"                       
                                                 );                       
                                                 printList();                       
           
                         // This code contributed by umadevi9616                       
           
                         </script>                       

输出：

List before removal of duplicates23 28 28 35 49 49 53 53 List after removal of duplicates23 35

时间复杂性： O（n）本文由 萨洛尼巴哈酒店 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章