试图修复程序中删除链接列表中重复项的错误

Question

我正在执行一个程序，用于使用两个循环从未排序的链表中删除重复项。

该程序包括用于定义CCD_ 2和CCD_ 3的两个CCD_。此外，它还包括两个用户定义函数removeDuplicates，用于删除链表的重复项，以及printList，用于打印列表。

struct Node {
int data;
struct Node *next;
};
struct Node *newNode(int data) {
Node *temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
};
/* Function to remove duplicates from an unsorted linked list */
void removeDuplicates(struct Node *start) {
struct Node *ptr1, *ptr2, *dup;
ptr1 = start;
while (ptr1 != NULL && ptr1->next != NULL) {
ptr2 = ptr1;
while (ptr2->next != NULL) {
if (ptr1->data == ptr2->next->data) {
dup = ptr2->next;
ptr2->next = ptr2->next->next;
delete (dup);
} else
ptr2 = ptr2->next;
ptr1 = ptr1->next;
}
}
}
void printList(struct Node *node) {
while (node != NULL) {
printf("%d  ", node->data);
node = node->next;
}
printf("n");
}

我运行了几个测试用例，

情况1输入：12->11->12->21->41->43->21

Output(from the program) : 12->11->12->21->41->43->21
Required Output : 12->11->21->41->43

int main() {
struct Node *start = newNode(12);
start->next = newNode(11);
start->next->next = newNode(12);
start->next->next->next = newNode(21);
start->next->next->next->next = newNode(41);
start->next->next->next->next->next = newNode(43);
start->next->next->next->next->next->next = newNode(21);
printf("Linked List before removing duplicates");
printList(start);
removeDuplicates(start);
printf("Linked List after removing duplicates");
printList(start);
}

情况2输入：10->12->11->11->12->11->10

Output : 10->12->11

int main() {
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);
}

该程序适用于一个测试用例，而不适用于其他用例。代码中缺少什么？

Answer 1

问题就在这里：

while ((ptr1 != NULL) && (ptr1->next != NULL))
{
ptr2 = ptr1;
while (ptr2->next != NULL)
{
// delete if duplicate
ptr1 = ptr1->next;
}
}

您正在移除重复项的循环中移动ptr1，但它需要在链表中的每个节点移动一次：

while ((ptr1 != NULL) && (ptr1->next != NULL))
{
ptr2 = ptr1;
while (ptr2->next != NULL)
{
// delete if duplicate
}
ptr1 = ptr1->next;  // move ptr1 here
}

这是一个演示。

Answer 2

/* Function to remove duplicates from an unsorted linked list*/
void removeDuplicates(struct Node *start)
{
struct Node *ptr1 = start;
while (ptr1) {

struct Node *ptr2     = ptr1->next;
struct Node *ptr2prev = ptr1;
while (ptr2) {
if (ptr1->data == ptr2->data) {

struct Node *tmp = ptr2;
ptr2prev->next   = ptr2->next;
ptr2             = ptr2->next;

delete tmp;
continue;
}  
ptr2 = ptr2->next;
ptr2prev = ptr2prev->next;
}  
ptr1 = ptr1->next;
}  
}

Answer 3

简短回答。以下代码将起作用。

void removeDuplicates(struct Node *start)
{
struct Node *ptr1, *ptr2, *ptr3;
ptr1 = start;
while ((ptr1 != NULL) )
{
ptr2 = ptr1->next;
ptr3=ptr1; //used inside the next while loop
while (ptr2 != NULL)
{
if ((ptr1->data) == (ptr2->data))
{
ptr3->next = ptr2->next;
delete (ptr2);
ptr2 = ptr3->next
}
else
{
ptr3 = ptr2; //prev of next ptr2
ptr2 = ptr2->next;
}
}
ptr1=ptr1->next;
}
}

您正在修改第一个while循环中的变量ptr1。由于必须将第一个元素与链表的所有剩余元素进行比较，因此只应在内部while循环完成后更改"ptr1"。否则，第一个节点将与第二个节点进行比较，然后将第一个节点修改为下一个节点。因此，第一个节点不会与其他节点进行比较。