C：从未排序的链表中删除重复项
我一直在研究这个问题的时间超过了我现在承认的时间，这让我疯了！ 给定一个简单的链表，比如除了指向下一个节点（ next ）的指针之外只存储一个整数（ data ），我想要一个算法去除重复，而不需要排序或依赖辅助函数。
以前的问题已经被问及Java中未分类的链表，它利用了Java提供的辅助function。 这与C无关，而不使用辅助函数。
我已经修改了代码并且已经将其用于某些情况，但不是全部。 这是一个完整的，可validation的示例 – 我包含了push()函数来创建链接列表和main()包含测试用例，但我的问题所涉及的逻辑仅在removeDuplicates() ：
#include #include struct node { int data; struct node *next; }; void push(struct node **headRef, int data) { struct node *newNode = malloc(sizeof(struct node)); newNode->data = data; newNode->next = *headRef; *headRef = newNode; } void removeDuplicates(struct node **head) { struct node *currentNode = *head; //The node we compare other nodes against struct node *runningNode = (*head)->next; //The node we are comparing to struct node *runningNodePrev = *head; //The node before the node we are comparing to struct node *runningNodeNext = (*head)->next->next; // The node after the node we are comparing to int count = -1; while (currentNode->next != NULL) { //Ensure we are not looking at the last node -- cannot have comparisons past this node count++; if (count) { //'Base Position' currentNode = currentNode->next; runningNodePrev = currentNode; runningNode = currentNode->next; runningNodeNext = runningNode->next; } printf("\nChecking for a match with %d ... \n", currentNode->data); while (runningNode != NULL) { //Compare each node in the list until we reach the end of the list printf("Inspecting next adjacent node ... \n"); if (runningNode->data == currentNode->data) {//If a duplicate is found printf("Found match ... "); //Ensure link is maintained before removing duplicate node if (currentNode == runningNodePrev) currentNode->next = runningNodeNext; runningNodePrev->next = runningNodeNext; free(runningNode);//Delete duplicate node printf("Deleted duplicate.\n"); } runningNode = runningNodeNext;//Continue searching for duplicates at the first unchecked node runningNodeNext = runningNodeNext->next;//Move running node leader up the list. } } } int main(void) { struct node *t1 = NULL; struct node *t2 = NULL; struct node *t4 = NULL; struct node *t5 = NULL; push(&t1, 1); push(&t1, 1); push(&t1, 1); push(&t1, 1); push(&t2, 6); push(&t2, 1); push(&t2, 2); push(&t2, 3); push(&t2, 4); push(&t2, 5); push(&t2, 6); push(&t4, 4); push(&t4, 2); push(&t4, 3); push(&t4, 2); push(&t4, 1); push(&t5, 0); push(&t5, 0); push(&t5, 1); printf("Testing removeDuplicates()...\n"); printf("Case 1: Calling removeDuplicates({1,0,0}).\n"); printf("Expected result: { 1 0 }\n"); printf("Actual result: { "); removeDuplicates(&t5); ptr = t5; while (ptr != NULL) { printf("%d ", ptr->data); ptr = ptr->next; } printf("}\n"); printf("Case 2: Calling removeDuplicates({1,2,3,2,4}).\n"); printf("Expected result: { 1 2 3 4 }\n"); printf("Actual result: { "); removeDuplicates(&t4); ptr = t4; while (ptr != NULL) { printf("%d ", ptr->data); ptr = ptr->next; } printf("}\n"); printf("Case 3: Calling removeDuplicates({6,5,4,3,2,1,6}).\n"); printf("Expected result: { 6 5 4 3 2 1 }\n"); printf("Actual result: { "); removeDuplicates(&t2); ptr = t2; while (ptr != NULL) { printf("%d ", ptr->data); ptr = ptr->next; } printf("}\n"); printf("Case 4: Calling removeDuplicates({1,1,1,1}).\n"); printf("Expected result: { 1 }\n"); printf("Actual result: { "); removeDuplicates(&t1); ptr = t1; while (ptr != NULL) { printf("%d ", ptr->data); ptr = ptr->next; } printf("}\n"); }
我还提供了一张描述逻辑的图片，如果不清楚我在做什么： http ： //imgur.com/DbnBOq2
/* Program to remove duplicates in an unsorted linked list */ #include 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 /* This is tricky */ 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; } } /* Druver program to test above function */ 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("\nLinked list after removing duplicates "); printList(start); return 0; }
参考： geeksforgeeks
void removeDuplicates(struct node **head){ struct node *tmp; while (*head) { /* Look below *head, to see if it has any duplicates */ for (tmp= (*head)->next; tmp; tmp = tmp->next) { if (tmp->data == (*head)->data) break; } /* Found no duplicate: advance head */ if(!tmp) { head = &(*head)->next; continue;} /* Duplicate found :: delete *head */ tmp = (*head)->next; free(*head); *head = tmp; } return; }
现在，检查角落案例：
- 如果* head为NULL，则永远不会执行外部循环：没有任何反应
- 如果（* head） – > next为NULL，则内部循环永远不会执行，因此在内循环后tmp仍为NULL
- 如果找到重复* head被替换为 – > next指针（可能为NULL）
- 如果没有找到重复，* head只是前进到它的 – >下一个指针（可能是NULL）
这种问题在各种变化中都有很多问题。 通常当一个人实现一个链表时，最终会出现一个需要保持指向各种元素的指针的点。 从表面上看，似乎单个重定向更容易使用，而实际上它并没有传达足够的关于列表的信息来在本地执行操作。
这是使用“链接”抽象（实际上是struct node** ）重写（但未完全测试）的struct node** ：
void removeDuplicates(struct node** head) { if(!head) return; struct node **link = head; // We will iterate over the links. Ie the `next` pointers in the list. while(*link) { struct node **rest = &((*link)->next); while(*rest) { if ((*link)->data != (*rest)->data) { rest = &((*rest)->next); // move to the next link } else { // modify the current link of rest to look one past the next struct node *to_remove = *rest; *rest = to_remove->next; free(to_remove); } } link = &((*link)->next); // again, move the the next link } }
通过使用另一个间接层，可以保证我们用于遍历列表的迭代器在任何时候都不会失效。 没有办法（除非写错误）上面的循环可以使*link无效，因此在赋值link = &((*link)->next);之前无需检查link = &((*link)->next);
特别感谢@StoryTeller – 我还没有validation你的解决方案，但你对有太多指针的评论绝对是关键。 我已经重新编写了我的函数，它现在适用于4种不同的特殊情况（列表末尾的复制品，列表的开头，整个列表中随机的列表，纯粹包含重复的列表）。 这是正确的代码：
void removeDuplicates(struct node** head){ struct node* currentNode = *head; struct node* runningNode = (*head)->next; struct node* runningNodePrev = *head; int count = -1; while(currentNode->next != NULL){ count++; if(count){ currentNode = currentNode->next; runningNodePrev = currentNode; runningNode = currentNode->next; } while(runningNode != NULL){ if(runningNode->data == currentNode->data){ runningNodePrev->next = runningNode->next; free(runningNode); runningNode = runningNodePrev->next; }else{ runningNodePrev = runningNodePrev->next; runningNode = runningNode->next; } } } }
干杯谢谢所有评论的人。