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

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 * O(N)= O(N2)

我强烈建议您自己尝试一下并练习。完成后，您可以阅读 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)。

我曾经将Merge Sort应用于 sort the list in C。也有 Remove duplicates from sorted list作为另一种解释。