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

编写一个removeDuplicates()函数，它接受一个链表并从链表中删除任何重复的节点。该链表未排序。

例如，如果链接列表是12- > 11- > 12- > 21- > 41- > 43- > 21，那么removeDuplicates()应将该列表转换为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
                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;
    }
}
 
// Driver code
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("Linked list after removing duplicates ");
    printList(start);
    return 0;
}  

输出：

在删除重复项之前的链接列表：
10 12 11 11 12 11 10 
删除重复项后的链接列表：
10 12 11

时间复杂度：O(n ^ 2)

辅助空间：O(1)

方法2（使用排序）：

一般来说，归并排序是最适合高效地对链表进行排序的排序算法。

1）使用Merge Sort对元素进行排序。我们将很快编写一篇有关对链接列表进行排序的文章。O(nLogn)

2）使用用于在排序的链接列表中删除重复项的算法在线性时间内删除重复项。O(n)

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

时间复杂度： O(nLogn)

方法3（使用哈希）：

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

// C++程序去除未排序链表中的重复项
#include
using namespace std;

// 链表节点
struct Node
{
    int data;
    struct Node *next;
};

// 创建新节点的实用程序函数
struct Node *newNode(int data)
{
   Node *temp = new Node;
   temp->data = data;
   temp->next = NULL;
   return temp;
}

/* 从未排序链表中删除重复项的函数 */
void removeDuplicates(struct Node *start)
{
    // 存储已经遍历过的值
    unordered_set seen;

    // 逐个选择元素
    struct Node *curr = start;
    struct Node *prev = NULL;
    while (curr != NULL)
    {
        // 如果当前值以前已经出现过，则删除当前节点
        if (seen.find(curr->data) != seen.end())
        {
           prev->next = curr->next;
           delete (curr);
        }
        else
        {
           seen.insert(curr->data);
           prev = curr;
        }
        curr = prev->next;
    }
}

// 给定链接列表中的节点，打印节点
void printList(struct Node *node)
{
    while (node != NULL)
    {
        printf("%d ", node->data);
        node = node->next;
    }
}

// 驱动程序
int main()
{
    /* 构建的链表如下所示：
       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("去除重复项前的链表：");
    printList(start);
    removeDuplicates(start);

    printf("去除重复项后的链表：");
    printList(start);
    return 0;
}  

输出：

去除重复项前的链表：
10 12 11 11 12 11 10
去除重复项后的链表：
10 12 11

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