I have been working on this problem for more hours than I'd like to admit now and it's driving me nuts! Given a simple linked list, say one that stores an integer (data) only in addition to a pointer to the next node (next), I would like an algorithm that removes duplicates without sorting or relying on helper functions.
Previous questions have been asked about unsorted linked lists in Java which take advantage of helper functions that Java offers. This is strictly pertinent to C without the use of helper functions.
I have tinkered around with code and have got this to work for some cases, but not all. Here is a complete, verifiable example -- I've include a push() function to create a linked list and a main() with test cases, but the logic that my question pertains to is in removeDuplicates() alone:
#include <stdlib.h>
#include <stdio.h>
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");
}
I've also included a picture that describes the logic if it is unclear what I'm doing: http://imgur.com/DbnBOq2
pushto not insert a duplicate?