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

分手后的思念是犯贱 2022-03-22 12:59 173阅读 0赞

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

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

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

> 欢迎大家加入粉丝群：963944895，群内免费分享Spring框架、Mybatis框架SpringBoot框架、SpringMVC框架、SpringCloud微服务、Dubbo框架、Redis缓存、RabbitMq消息、JVM调优、Tomcat容器、MySQL数据库教学视频及架构学习思维导图

#### 写在最后： ####

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