我有一个链表，我想删除重复值

Question

所以，我创建了一个代码，它创建了一个包含 5 个值的链表。我想知道删除这些值的重复项并在没有重复项的情况下再次打印链接列表的最佳方法是什么。

#include <stdio.h>
#include <stdlib.h>

/* self-referential structure*/
struct studentID{
    int value;          //a data member which is an integer
    struct studentID *next;         //a data member which is a pointer to next node
};


typedef struct studentID STUDENTID;     //creating a nickname for struct studentID as STUDENTID
typedef STUDENTID *STUDENTIDPtr;        //creating a nickname for STUDENTID as STUDENTIDPtr


//Global variables
STUDENTIDPtr previousPtr;           //pointer to previous node in list
STUDENTIDPtr currentPtr;            //pointer to current node in list


void printList(STUDENTIDPtr currentPtr){


    while (currentPtr != NULL){         //while not the end of the list
        printf("%d -> ", currentPtr->value);
        currentPtr = currentPtr ->next;
    }
}


int main(){
    STUDENTIDPtr newPtr1;           //creating a pointer to create a new node
    STUDENTIDPtr newPtr2;           //creating a pointer to create a new node
    STUDENTIDPtr newPtr3;           //creating a pointer to create a new node
    STUDENTIDPtr newPtr4;           //creating a pointer to create a new node
    STUDENTIDPtr newPtr5;           //creating a pointer to create a new node


    //creation of the first node
    newPtr1 = malloc(sizeof(STUDENTID));            //This is when a node is created
    newPtr2 = malloc(sizeof(STUDENTID));            //This is when a node is created
    newPtr3 = malloc(sizeof(STUDENTID));            //This is when a node is created
    newPtr4 = malloc(sizeof(STUDENTID));            //This is when a node is created
    newPtr5 = malloc(sizeof(STUDENTID));            //This is when a node is created


    newPtr1 -> value = 4; // assign data in first node 
    newPtr1 -> next = newPtr2;


    newPtr2 -> value = 4; // assign data in first node 
    newPtr2 -> next = newPtr3;


    newPtr3 -> value = 5; // assign data in first node 
    newPtr3 -> next = newPtr4;


    newPtr4 -> value = 2; // assign data in first node 
    newPtr4 -> next = newPtr5;


    newPtr5 -> value = 1; // assign data in first node 
    newPtr5 -> next = NULL;


    currentPtr = newPtr1;

    printList(newPtr1);


    return 0;
}

在每个链表中使用 if else 和运行是否容易，或者是否有更好的方法？

Answer 1

马上想到了两种方法，使用哪一种取决于您的具体情况，以及您是否想要保留元素的原始顺序。

第一种方法：

使用双循环，一次拾取一个节点。然后在该节点之后迭代列表，如果找到重复项，则将其删除。重复选取节点，直到遍历整个列表。

For every node of the list
  For every next_node after node
    If next_node.value == node.value
      Remove that next_node

这种方法保留了元素的原始顺序。

我认为您已经想到了这种方法。我建议你从那开始。

示例：

1 -> 2 -> 3 -> 4 -> 1

我将从第一个节点（1）开始，检查第二个节点，第三个，第四个，目前没有，没有找到重复项。我现在检查第五个节点，它的值也是 1（发现重复项！），所以我将其删除。

现在列表如下所示：

1 -> 2 -> 3 -> 4

现在我正在查找第二个节点的副本（我在之前的遍历中检查了第一个节点）。我检查 3，我检查 4，没有找到重复项。列表保持不变。

现在我正在查找第三个节点的副本。我检查 4，没有找到重复项。列表保持不变。

现在我正在查找第四个节点的副本。下一个节点为NULL，也就是说第四个节点是最后一个节点（因为我们在第一次遍历的时候去掉了第五个节点，作为1的副本）。没有什么可检查的，列表保持不变：

1 -> 2 -> 3 -> 4

观察如何，对于我想要检查是否存在重复项的每个节点，我遍历列表直到它的末尾。因此，对于每个节点，我都在进行 O(N) 遍历，其中 N 是列表的大小。

我有多少个节点？ N

所以这种方法的时间复杂度是 N * O(N) = O(N²)

我强烈建议您亲自尝试并练习。完成后，您可以阅读 Remove duplicates from an unsorted list 来检查您的解决方案。

第二种方法：

对列表进行排序，现在列表会将重复的值组合在一起。所以，如果当前节点有副本，它将成为它的下一个节点。如果重复，删除下一个节点。

现在，再说一次，如果当前节点有副本，它将成为它的下一个节点。所以做同样的事情，直到下一个节点不是当前节点的副本。

然后，将下一个节点设为当前节点，做同样的处理。

Sort list
current_node = head_node
While current_node != NULL
  If current_node.value == current_node.next.value
    Remove current_node.next
  Else
    current_node = current_node.next

此方法不保留元素的原始顺序。

同一个例子：

1 -> 2 -> 3 -> 4 -> 1

对列表进行排序：

1 -> 1 -> 2 -> 3 -> 4

我从1开始，我查看它的下一个节点，也是1，发现重复！删除下一个节点。现在列表是：

1 -> 2 -> 3 -> 4

当前节点还是1，我查看它的下一个节点，是2，不是重复的。列表保持不变。将下一个节点设置为当前节点。

当前节点是2，查看下一个节点，是3，不是重复的。列表保持不变。将下一个节点设置为当前节点。

当前节点是3，查看下一个节点，是4，不是重复的。列表保持不变。将下一个节点设置为当前节点。

当前节点是4。它没有下一个节点，没有什么可检查的，我完成了。列表保持不变：

1 -> 2 -> 3 -> 4

观察到对于每个节点，我只检查它的直接下一个节点。然后，我继续检查最后一个下一个节点。即O(N)。

但是，我必须对列表进行排序，以确保重复项被分组。可以在 O(NlogN) 中对列表进行排序。

时间复杂度为 O(NlogN) + O(N) = O(NlogN)。

我曾使用合并排序来 sort the list in C. There is also the Remove duplicates from sorted list 进行另一种解释。

Answer 2

以下解决方案仅适用于足够小的整数值，不适用于非常大的整数值。我们在这里可以做的是采用另一个可以充当关联容器的数组。

取一个数组。将该数组初始化为 0。
开始遍历链表
if (arr[节点->数据] == 0);然后递增 arr[node->data]。这将使它成为 1，标记一次出现。
else if (arr[node->data] == 1);然后删除这个节点，因为这意味着当前节点已经包含一个以前遇到过的整数。

您可以实现基于散列或 BST 的 DS，类似于 cpp 映射，以充当关联容器，如果您想扩大规模。

如果您想要一个通用算法，我建议您首先按照以下几行编写一个强力逻辑 --

遍历链表
如果第一次找到'data'，则忽略并继续。
如果下次找到'data'，则调用删除逻辑。

Answer 3

在发布的代码中，您 "manually" 添加列表前面的每个节点，因此第一步是创建一个执行此操作的函数。

然后，您可以创建另一个函数，该函数将在列表中添加一个节点以保持排序。它将遍历列表以找到正确的位置，并且仅当该节点不存在时才会添加另一个具有相同值的节点。

现在您可以遍历原始列表（未排序的列表），并为每个节点尝试将其副本添加到已排序的列表中。如果它已经存在，则从原始列表中删除该节点，否则将副本添加到排序列表中。

最后您将得到两个唯一元素列表，其中一个已排序。

不要忘记创建一个函数来释放分配的内存。

Answer 4

您的意思似乎不仅是删除列表中相邻的重复值。

您需要编写一个函数，通过引用接受列表的头节点。该函数可以return删除节点的数量。

注意声明全局变量是个坏主意

//Global variables
STUDENTIDPtr previousPtr;           //pointer to previous node in list
STUDENTIDPtr currentPtr;            //pointer to current node in list

而且是多余的。

而且这个 typedef 会使代码的读者感到困惑

typedef STUDENTID *STUDENTIDPtr;

您也可以编写一个单独的函数来将节点添加到列表中。您最初可以编写函数，使列表中的节点按值排序。

至于删除重复值的函数，那么它可以看起来像下面的演示程序中所示的方式。调查一下。

#include <stdio.h>
#include <stdlib.h>

/* self-referential structure*/
struct studentID{
    int value;          //a data member which is an integer
    struct studentID *next;         //a data member which is a pointer to next node
};


typedef struct studentID STUDENTID;     //creating a nickname for struct studentID as STUDENTID
typedef STUDENTID *STUDENTIDPtr;  

size_t remove_duplicates( STUDENTIDPtr *head )
{
    size_t n = 0;

    for ( ; *head != NULL; head = &( *head )->next )
    {
        for ( STUDENTIDPtr *next = &( *head )->next; *next != NULL; )
        {
            if ( ( *head )->value == ( *next )->value )
            {
                STUDENTIDPtr tmp = *next;
                *next = ( *next )->next;
                free( tmp );
                ++n;
            }
            else
            {
                next = &( *next )->next;
            }
        }
    }

    return n;
}

void printList(STUDENTIDPtr currentPtr){


    for ( ; currentPtr != NULL; currentPtr = currentPtr ->next )
    {
        printf("%d -> ", currentPtr->value);
    }

    puts( "NULL" );
}

int main(void) 
{
    STUDENTIDPtr newPtr1;           //creating a pointer to create a new node
    STUDENTIDPtr newPtr2;           //creating a pointer to create a new node
    STUDENTIDPtr newPtr3;           //creating a pointer to create a new node
    STUDENTIDPtr newPtr4;           //creating a pointer to create a new node
    STUDENTIDPtr newPtr5;           //creating a pointer to create a new node


    //creation of the first node
    newPtr1 = malloc(sizeof(STUDENTID));            //This is when a node is created
    newPtr2 = malloc(sizeof(STUDENTID));            //This is when a node is created
    newPtr3 = malloc(sizeof(STUDENTID));            //This is when a node is created
    newPtr4 = malloc(sizeof(STUDENTID));            //This is when a node is created
    newPtr5 = malloc(sizeof(STUDENTID));            //This is when a node is created


    newPtr1 -> value = 4; // assign data in first node 
    newPtr1 -> next = newPtr2;


    newPtr2 -> value = 4; // assign data in first node 
    newPtr2 -> next = newPtr3;


    newPtr3 -> value = 5; // assign data in first node 
    newPtr3 -> next = newPtr4;


    newPtr4 -> value = 2; // assign data in first node 
    newPtr4 -> next = newPtr5;


    newPtr5 -> value = 1; // assign data in first node 
    newPtr5 -> next = NULL;


    printList( newPtr1 );

    size_t n = remove_duplicates( &newPtr1 );

    printf( "There are removed %zu elements\n", n );

    printList( newPtr1 );

    return 0;
}

程序输出可能看起来像

4 -> 4 -> 5 -> 2 -> 1 -> NULL
There are removed 1 elements
4 -> 5 -> 2 -> 1 -> NULL

请记住，您还需要编写一个函数来为列表释放所有分配的内存。

我有一个链表，我想删除重复值

I have a linked list, I would like to remove duplicate values

c

algorithm

struct

linked-list

singly-linked-list