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

因此该方法的时间复杂度为 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 。还有Remove duplicates from sorted list另一种解释。