有一个带头结点的单链表，设计算法删除单链表中所以重复出现的结点，使得整型域相

发布网友发布时间：2022-12-21 08:32

共1个回答

热心网友时间：2023-10-10 01:07

//C/C++实现，从原链表中取不重复的放到另一个链表里，每个节点都从头开始比较(性能较差)，释放原链表
//删除重复节点
typedef struct tagMyList
{
    int data;
    struct tagMyList *next;
}MyList;
MyList* deleteRepeatNode(MyList *l);
void freeList(MyList *l)
{
    MyList *t = l->next;
    while (t)
    {
        MyList *t_next = t->next;
        free(t);
        t = t_next;
    }
}
void printfList(MyList *l)
{
    MyList *t = l->next;
    while (t)
    {
        printf("%d ", t->data);
        t = t->next;
    }
    printf("\n");
}
/*
test:
input:  4 2 3 3 4 4 0 4 2 1
output: 0 1
*/
void deleteRepeatNodeTest()
{
    int length = 10;
    MyList *result;
    MyList *l = (MyList *)malloc(sizeof(MyList));
    l->next = NULL;
    for (int i = 0; i < length; i++)
    {
        MyList *t = (MyList *)malloc(sizeof(MyList));
        t->data = rand()%5;
        t->next = l->next;
        l->next = t;
    }
    printfList(l);
    result = deleteRepeatNode(l);
    printfList(result);
}
/*
* 算法方式，从原链表中取不重复的放到另一个链表里，
*/
MyList* deleteRepeatNode(MyList *l)
{
    MyList *head = l;

    MyList *p1 = head->next;
    MyList *p2 = p1;
    MyList *p2_prev = head;
    MyList *pResult = NULL;
    MyList *pResultTail = NULL;
    while (p2)
    {
        p1 = head->next;
        while (p1)
        {
            if (p2 != p1 && p1->data == p2->data)
            {
                break;
            }
            p1 = p1->next;
        }
        if (p1 == NULL)
        {
            if (p2 == head->next)
            {
                head->next = p2->next;
            }
            else
            {
                p2_prev->next = p2->next;
            }
            if (pResult == NULL)
            {
                pResult = p2;
                pResultTail = pResult;
                pResultTail->next = NULL;
            }
            else
            {
                pResultTail->next = p2;
                pResultTail = p2;
                pResultTail->next = NULL;
            }
            p2 = p2_prev->next;

        }
        else
        {
            p2_prev = p2;
            p2 = p2->next;
        }
    }
    freeList(head);
    head->next = pResult;
    return head;
}