C:从未排序的链表中删除重复项

Question

我已经在这个问题上工作了比我现在愿意承认的更多的时间，这让我抓狂!给定一个简单的链表，比如一个除了指向下一个节点 (next) 的指针之外只存储一个整数 (data) 的链表，我想要一个算法来删除无需排序或依赖辅助函数即可复制。

以前的问题是关于 Java 中未排序的链表，它利用了 Java 提供的辅助函数。在不使用辅助函数的情况下，这与 C 严格相关。

我对代码进行了修改，并使其适用于某些情况，但并非全部。这是一个完整的、可验证的示例——我包含了一个用于创建链表的 push() 函数和一个带有测试用例的 main()，但是逻辑我的问题与 removeDuplicates() 单独有关:

#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");
}

如果不清楚我在做什么，我还提供了一张描述逻辑的图片:http://imgur.com/DbnBOq2

Answer 1

/* Program to remove duplicates in an unsorted linked list */

#include <bits/stdc++.h>
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