从未排序的链表中删除重复项

栏目: 数据库 · 发布时间: 6年前

内容简介：编写一个removeduplicates（）函数，该函数获取一个列表并从列表中删除所有重复的节点。列表未排序。例如，如果链表是12->11->12->21->41->43->21，那么removeUplicates（）应该将链表转换为12->11->21->41->43。建议：请先在“实践”中解决，然后再继续解决问题。

编写一个removeduplicates（）函数，该函数获取一个列表并从列表中删除所有重复的节点。列表未排序。

例如，如果链表是12->11->12->21->41->43->21，那么removeUplicates（）应该将链表转换为12->11->21->41->43。

建议：请先在“实践”中解决，然后再继续解决问题。

方法1（使用两个回路）

这是使用两个循环的简单方法。外循环用于逐个选取元素，内循环将选取的元素与其余元素进行比较。

感谢Gaurav Saxena在编写此代码方面的帮助。

C++

<font><i>/* Program to remove duplicates in an unsorted 
   linked list */</i></font><font>
#include<bits/stdc++.h> 
using namespace std; 
  
</font><font><i>/* A linked list node */</i></font><font>
struct Node 
{ 
    <b>int</b> data; 
    struct Node *next; 
}; 
  
</font><font><i>// Utility function to create a new Node </i></font><font>
struct Node *newNode(<b>int</b> data) 
{ 
   Node *temp = <b>new</b> Node; 
   temp->data = data; 
   temp->next = NULL; 
   <b>return</b> temp; 
} 
  
</font><font><i>/* Function to remove duplicates from a 
   unsorted linked list */</i></font><font>
<b>void</b> removeDuplicates(struct Node *start) 
{ 
    struct Node *ptr1, *ptr2, *dup; 
    ptr1 = start; 
  
    </font><font><i>/* Pick elements one by one */</i></font><font>
    <b>while</b> (ptr1 != NULL && ptr1->next != NULL) 
    { 
        ptr2 = ptr1; 
  
        </font><font><i>/* Compare the picked element with rest 
           of the elements */</i></font><font>
        <b>while</b> (ptr2->next != NULL) 
        { 
            </font><font><i>/* If duplicate then delete it */</i></font><font>
            <b>if</b> (ptr1->data == ptr2->next->data) 
            { 
                </font><font><i>/* sequence of steps is important here */</i></font><font>
                dup = ptr2->next; 
                ptr2->next = ptr2->next->next; 
                delete(dup); 
            } 
            <b>else</b> </font><font><i>/* This is tricky */</i></font><font>
                ptr2 = ptr2->next; 
        } 
        ptr1 = ptr1->next; 
    } 
} 
  
</font><font><i>/* Function to print nodes in a given linked list */</i></font><font>
<b>void</b> printList(struct Node *node) 
{ 
    <b>while</b> (node != NULL) 
    { 
        printf(</font><font>"%d "</font><font>, node->data); 
        node = node->next; 
    } 
} 
  
</font><font><i>/* Druver program to test above function */</i></font><font>
<b>int</b> main() 
{ 
    </font><font><i>/* The constructed linked list is: 
     10->12->11->11->12->11->10*/</i></font><font>
    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(</font><font>"Linked list before removing duplicates "</font><font>); 
    printList(start); 
  
    removeDuplicates(start); 
  
    printf(</font><font>"\nLinked list after removing duplicates "</font><font>); 
    printList(start); 
  
    <b>return</b> 0; 
}
</font>

JAVA

<font><i>// Java program to remove duplicates from unsorted  </i></font><font>
</font><font><i>// linked list </i></font><font>
  
<b>class</b> LinkedList { 
  
    <b>static</b> Node head; 
  
    <b>static</b> <b>class</b> Node { 
  
        <b>int</b> data; 
        Node next; 
  
        Node(<b>int</b> d) { 
            data = d; 
            next = <b>null</b>; 
        } 
    } 
  
    </font><font><i>/* Function to remove duplicates from an 
       unsorted linked list */</i></font><font>
    <b>void</b> remove_duplicates() { 
        Node ptr1 = <b>null</b>, ptr2 = <b>null</b>, dup = <b>null</b>; 
        ptr1 = head; 
  
        </font><font><i>/* Pick elements one by one */</i></font><font>
        <b>while</b> (ptr1 != <b>null</b> && ptr1.next != <b>null</b>) { 
            ptr2 = ptr1; 
  
            </font><font><i>/* Compare the picked element with rest 
                of the elements */</i></font><font>
            <b>while</b> (ptr2.next != <b>null</b>) { 
  
                </font><font><i>/* If duplicate then delete it */</i></font><font>
                <b>if</b> (ptr1.data == ptr2.next.data) { 
  
                    </font><font><i>/* sequence of steps is important here */</i></font><font>
                    dup = ptr2.next; 
                    ptr2.next = ptr2.next.next; 
                    System.gc(); 
                } <b>else</b> </font><font><i>/* This is tricky */</i></font><font> { 
                    ptr2 = ptr2.next; 
                } 
            } 
            ptr1 = ptr1.next; 
        } 
    } 
  
    <b>void</b> printList(Node node) { 
        <b>while</b> (node != <b>null</b>) { 
            System.out.print(node.data + </font><font>" "</font><font>); 
            node = node.next; 
        } 
    } 
  
    <b>public</b> <b>static</b> <b>void</b> main(String args) { 
        LinkedList list = <b>new</b> LinkedList(); 
        list.head = <b>new</b> Node(10); 
        list.head.next = <b>new</b> Node(12); 
        list.head.next.next = <b>new</b> Node(11); 
        list.head.next.next.next = <b>new</b> Node(11); 
        list.head.next.next.next.next = <b>new</b> Node(12); 
        list.head.next.next.next.next.next = <b>new</b> Node(11); 
        list.head.next.next.next.next.next.next = <b>new</b> Node(10); 
  
        System.out.println(</font><font>"Linked List before removing duplicates : \n "</font><font>); 
        list.printList(head); 
  
        list.remove_duplicates(); 
        System.out.println(</font><font>""</font><font>); 
        System.out.println(</font><font>"Linked List after removing duplicates : \n "</font><font>); 
        list.printList(head); 
    } 
} 
</font><font><i>// This code has been contributed by Mayank Jaiswal </i></font><font>
</font>

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

<font><i>/* Program to remove duplicates in an unsorted 
   linked list */</i></font><font>
#include<bits/stdc++.h> 
using namespace std; 
  
</font><font><i>/* A linked list node */</i></font><font>
struct Node 
{ 
    <b>int</b> data; 
    struct Node *next; 
}; 
  
</font><font><i>// Utility function to create a new Node </i></font><font>
struct Node *newNode(<b>int</b> data) 
{ 
   Node *temp = <b>new</b> Node; 
   temp->data = data; 
   temp->next = NULL; 
   <b>return</b> temp; 
} 
  
</font><font><i>/* Function to remove duplicates from a 
   unsorted linked list */</i></font><font>
<b>void</b> removeDuplicates(struct Node *start) 
{ 
    </font><font><i>// Hash to store seen values </i></font><font>
    unordered_set<<b>int</b>> seen; 
  
    </font><font><i>/* Pick elements one by one */</i></font><font>
    struct Node *curr = start; 
    struct Node *prev = NULL; 
    <b>while</b> (curr != NULL) 
    { 
        </font><font><i>// If current value is seen before </i></font><font>
        <b>if</b> (seen.find(curr->data) != seen.end()) 
        { 
           prev->next = curr->next; 
           delete (curr); 
        } 
        <b>else</b>
        { 
           seen.insert(curr->data); 
           prev = curr; 
        } 
        curr = prev->next; 
    } 
} 
  
</font><font><i>/* Function to print nodes in a given linked list */</i></font><font>
<b>void</b> printList(struct Node *node) 
{ 
    <b>while</b> (node != NULL) 
    { 
        printf(</font><font>"%d "</font><font>, node->data); 
        node = node->next; 
    } 
} 
  
</font><font><i>/* Driver program to test above function */</i></font><font>
<b>int</b> main() 
{ 
    </font><font><i>/* The constructed linked list is: 
     10->12->11->11->12->11->10*/</i></font><font>
    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(</font><font>"Linked list before removing duplicates : \n"</font><font>); 
    printList(start); 
  
    removeDuplicates(start); 
  
    printf(</font><font>"\nLinked list after removing duplicates : \n"</font><font>); 
    printList(start); 
  
    <b>return</b> 0; 
} 
</font>

JAVA

<font><i>// Java program to remove duplicates </i></font><font>
</font><font><i>// from unsorted linkedlist </i></font><font>
  
<b>import</b> java.util.HashSet; 
  
<b>public</b> <b>class</b> removeDuplicates  
{ 
    <b>static</b> <b>class</b> node  
    { 
        <b>int</b> val; 
        node next; 
  
        <b>public</b> node(<b>int</b> val)  
        { 
            <b>this</b>.val = val; 
        } 
    } 
      
    </font><font><i>/* Function to remove duplicates from a 
       unsorted linked list */</i></font><font>
    <b>static</b> <b>void</b> removeDuplicate(node head)  
    { 
        </font><font><i>// Hash to store seen values </i></font><font>
        HashSet<Integer> hs = <b>new</b> HashSet<>(); 
      
        </font><font><i>/* Pick elements one by one */</i></font><font>
        node current = head; 
        node prev = <b>null</b>; 
        <b>while</b> (current != <b>null</b>)  
        { 
            <b>int</b> curval = current.val; 
              
             </font><font><i>// If current value is seen before </i></font><font>
            <b>if</b> (hs.contains(curval)) { 
                prev.next = current.next; 
            } <b>else</b> { 
                hs.add(curval); 
                prev = current; 
            } 
            current = current.next; 
        } 
  
    } 
      
    </font><font><i>/* Function to print nodes in a given linked list */</i></font><font>
    <b>static</b> <b>void</b> printList(node head)  
    { 
        <b>while</b> (head != <b>null</b>)  
        { 
            System.out.print(head.val + </font><font>" "</font><font>); 
            head = head.next; 
        } 
    } 
  
    <b>public</b> <b>static</b> <b>void</b> main(String args)  
    { 
        </font><font><i>/* The constructed linked list is: 
         10->12->11->11->12->11->10*/</i></font><font>
        node start = <b>new</b> node(10); 
        start.next = <b>new</b> node(12); 
        start.next.next = <b>new</b> node(11); 
        start.next.next.next = <b>new</b> node(11); 
        start.next.next.next.next = <b>new</b> node(12); 
        start.next.next.next.next.next = <b>new</b> node(11); 
        start.next.next.next.next.next.next = <b>new</b> node(10); 
  
        System.out.println(</font><font>"Linked list before removing duplicates :"</font><font>); 
        printList(start); 
  
        removeDuplicate(start); 
  
        System.out.println(</font><font>"\nLinked list after removing duplicates :"</font><font>); 
        printList(start); 
    } 
} 
  
</font><font><i>// This code is contributed by Rishabh Mahrsee </i></font><font>
</font>

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)）。

以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。

码农书籍

Invisible Users

Jenna Burrell / The MIT Press / 2012-5-4 / USD 36.00

The urban youth frequenting the Internet cafes of Accra, Ghana, who are decidedly not members of their country's elite, use the Internet largely as a way to orchestrate encounters across distance and ......一起来看看《Invisible Users》这本书的介绍吧!

码农工具

正则表达式在线测试

RGB HSV 转换

RGB HSV 互转工具

HEX HSV 转换工具

HEX HSV 互换工具