递归删除链表中的重复元素

Kon 发表于 Dev

128

可以

我试图使用递归概念删除排序链表中的重复元素。

我想看看如何删除排序链表中的元素。我编写了一个代码，在该代码中应释放if head->data == head->next->datathan，head->next直到获得不同的元素为止。现在，我进行了许多更改，令我感到困惑。它会删除每个重复的值，而只在整个代码中只出现一次。

还请告诉我为什么此代码会这样做，以及代码有什么问题以及是否有可能以最佳方式完成相同的事情。

（我仅在deleteduplicate需要提供整个代码（例如打印列表或插入列表中）的情况下提供该功能，如果告诉我，将对其进行编辑）。

谢谢。

Node *deleteDuplicates(Node *head) { 
    if (head == NULL || head->next == NULL) {
        return head;
    }
    if (head->data == head->next->data) {
        struct Node *x = head->next;
        head->next = head->next->next;
        free(x);
        return deleteDuplicates(head);
    } else
        return deleteDuplicates(head->next);
}

输入： 11 11 11 13 13 20

输出： 20

预期产量： 11 13 20

chqrlie

此函数无需递归。只需在循环中迭代即可删除下一个元素或跳到下一个元素：

Node *deleteDuplicates(Node *head) {
    if (head != NULL) {
        Node *p = head;
        while (p->next) {
            if (p->next->data == p->data) {
                Node *x = p->next;
                p->next = x->next;
                free(x);
            } else {
                p = p->next;
            }
        }
    }
    return head;
}

您可以修复递归函数，但是应该对其进行修改以不返回头节点，因为这会阻止尾部递归，因此可能需要大量的堆栈空间。足够长的列表将导致堆栈溢出。

这是修改后的递归函数：

void deleteDuplicates(Node *head) { 
    if (head != NULL && head->next != NULL) {
        if (head->data == head->next->data) {
            struct Node *x = head->next;
            head->next = x->next;
            free(x);
            deleteDuplicates(head);
        } else {
            deleteDuplicates(head->next);
        }
    }
}

在你的代码的问题是，你的返回值保存deleteDuplicates到你的head指针，但该函数返回的指针到列表中的最后一个节点，而不是头节点。

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。