删除排序链表中的重复元素

Question

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode* p=head;
    while(p->next != NULL)
    {
        if(p->val == p->next->val)
        {
            p->next = p->next->next;
        }
        else
        {
            p=p->next;
        }
    }
    return head;
}

struct ListNode* deleteDuplicates(struct ListNode* head) {
    if(head == NULL || head->next == NULL)
    {
        return head;
    }
    struct ListNode* p=head->next;
    while(p != NULL)
    {
        if(p->val == p->next->val)
        {
            p->next = p->next->next;
        }
        else
        {
            p=p->next;
        }
    }
    return head;
}

为什么第2份报Line 16: Char 29: runtime error: member access within null pointer of type 'struct ListNode' [solution.c]循环判断体设置有什么问题

Answer 1

引自免费微信小程序：皆我百晓生

在C语言中，删除排序链表中的重复元素的代码可以通过动态规划的思想解决。以下是一个实现方案：

首先，我们定义一个名为ListNode的结构体，包含节点的值（val）和指向下一个节点的指针（next）。这个结构体将用于存储链表中的每一个节点。

下面是修改后的deleteDuplicates函数：

#include <stdio.h>
#include <stdlib.h>

// 定义 ListNode 结构体
struct ListNode {
    int val;
    struct ListNode *next;
};

// 原始链表
struct ListNode* head;

// 删除排序链表中的重复元素
void deleteDuplicates(struct ListNode** head) {
    // 初始化结果头指针为 head
    struct ListNode* result_head = *head;

    // 创建一个空的结果链表
    struct ListNode* result = nullptr;

    // 使用双指针算法遍历原链表
    for (struct ListNode* node = *head; node != NULL; node = node->next) {
        // 如果当前节点的值等于前一个节点的值，则跳过它
        if (node->val == result_head->val) {
            continue;
        }

        // 否则，将当前节点添加到结果链表末尾
        result = node->next;
    }

    // 将结果链表的头指针指向新的原始链表的头部
    *head = result_head->next;

    // 返回新链表的头指针
    return result_head;
}

int main() {
    // 初始化原始链表
    struct ListNode* head = createLinkedList();

    // 删除排序链表中的重复元素
    deleteDuplicates(&head);

    printf("Original list after deletion: ");
    printList(head);

    return 0;
}

// 创建一个简单的链表
struct ListNode* createLinkedList() {
    struct ListNode* node = (struct ListNode*) malloc(sizeof(struct ListNode));
    node->val = 1;
    node->next = nullptr;

    return node;
}

// 打印原始链表
void printList(struct ListNode* head) {
    struct ListNode* current = head;
    while (current != NULL) {
        printf("%d ", current->val);
        current = current->next;
    }
    printf("\n");
}

在这个解决方案中，我们首先初始化了一个结果头指针为原始链表的头部。然后，我们使用双指针算法遍历原链表。对于每个节点，如果其值等于结果头指针的值，我们就跳过它，因为在这种情况下，它们已经重复了。否则，我们将当前节点添加到结果链表末尾。

在主函数main中，我们创建了一个简单的链表并调用了deleteDuplicates函数删除重复元素，最后打印出了原链表。这段代码应该能正确地工作，删除任何已经存在于排序链表中的重复元素。注意，在实际应用中，如果链表非常大，此方法可能会占用大量的内存空间，并且时间复杂度也是O(n^2)，其中n是链表的长度。如果你需要处理大型数据集，可能需要使用其他更高效的方法，例如哈希表、集合操作等。