【本人秃顶程序员】从未排序的链表中删除重复项

作者: 本人秃顶程序员 | 来源:发表于2019-01-28 15:09 被阅读1次

←←←←←←←←←←←← 快！点关注

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

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

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

方法1（使用两个回路）

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

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

C++

/* Program to remove duplicates in an unsorted 
   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 remove duplicates from a 
   unsorted linked list */
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  
// linked list 
  
class LinkedList { 
  
    static Node head; 
  
    static class Node { 
  
        int data; 
        Node next; 
  
        Node(int d) { 
            data = d; 
            next = null; 
        } 
    } 
  
    /* Function to remove duplicates from an 
       unsorted linked list */
    void remove_duplicates() { 
        Node ptr1 = null, ptr2 = null, dup = null; 
        ptr1 = head; 
  
        /* 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) { 
        LinkedList list = new LinkedList(); 
        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.printList(head); 
  
        list.remove_duplicates(); 
        System.out.println(""); 
        System.out.println("Linked List after removing duplicates : \n "); 
        list.printList(head); 
    } 
} 
// This code has been contributed by Mayank Jaiswal

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是最适合用于有效排序链表的排序算法。

使用Merge Sort对元素进行排序。我们很快就会写一篇关于排序链表的帖子。O(nLogn）
使用用于删除已排序的链接列表中的重复项的算法，以线性时间删除重复项。O(n)

请注意，此方法不保留元素的原始顺序。

时间复杂度：O(nLogn)

方法3（使用哈希）

我们从头到尾遍历链接列表。对于每个新遇到的元素，我们检查它是否在哈希表中：如果是，我们将其删除; 否则我们把它放在哈希表中。

C++

/* Program to remove duplicates in an unsorted 
   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 remove duplicates from a 
   unsorted linked list */
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 
// from unsorted linkedlist 
  
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 
       unsorted linked list */
    static void removeDuplicate(node head)  
    { 
        // Hash to store seen values 
        HashSet<Integer> hs = new HashSet<>(); 
      
        /* Pick elements one by one */
        node current = head; 
        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 { 
                hs.add(curval); 
                prev = current; 
            } 
            current = current.next; 
        } 
  
    } 
      
    /* Function to print nodes in a given linked list */
    static void printList(node head)  
    { 
        while (head != null)  
        { 
            System.out.print(head.val + " "); 
            head = head.next; 
        } 
    } 
  
    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 
Output :
Linked list before removing duplicates:
 10 12 11 11 12 11 10 
Linked list after removing duplicates:
 10 12 11

时间复杂度：平均为O(n)（假设哈希表访问时间平均为O(1)）。

写在最后：

秃顶程序员的不易，看到这里，点了关注吧！
点关注，不迷路，持续更新！！！

【本人秃顶程序员】从未排序的链表中删除重复项

方法1（使用两个回路）

方法2（使用排序）

方法3（使用哈希）

写在最后：

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

互联网科技

Spring-Boot

java高级开发群

Java学习笔记

Java 杂谈

开发技巧