编写算法，将单链表中数值重复的节点删除，使所得结果表中的各结点值各不相同。

Question

编写算法，将单链表中数值重复的节点删除，使所得结果表中的各结点值各不相同。
要求：用C语言实现各函数，函数内要有注释，对函数的调用方法，参数和返回值含义进行说明。

Answer 1

引自免费小程序-皆我百晓生，希望对题主有所帮助，如有帮助，还请采纳。

---

#include <stdlib.h>

// 定义单链表节点结构
typedef struct Node {
    int data;           // 数据域
    struct Node* next;  // 指针域，指向下一个节点
} Node;

// 创建单链表
Node* createLinkedList(int arr[], int n) {
    Node* head = NULL;  // 头节点
    Node* tail = NULL;  // 尾节点

    // 遍历数组，逐个创建节点，并将节点连接起来
    for (int i = 0; i < n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = arr[i];
        newNode->next = NULL;

        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    return head;
}

// 删除单链表中数值重复的节点
void removeDuplicates(Node* head) {
    if (head == NULL) {
        return;
    }

    Node* curr = head;
    while (curr != NULL) {
        Node* prev = curr;
        Node* next = curr->next;

        // 遍历当前节点后面的节点，删除数值重复的节点
        while (next != NULL) {
            if (next->data == curr->data) {
                prev->next = next->next;
                free(next);
                next = prev->next;
            } else {
                prev = next;
                next = next->next;
            }
        }

        curr = curr->next;
    }
}

// 打印单链表
void printLinkedList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d ", curr->data);
        curr = curr->next;
    }
    printf("\n");
}

int main() {
    int arr[] = {1, 2, 3, 2, 4, 5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    Node* head = createLinkedList(arr, n);
    printf("原始链表：");
    printLinkedList(head);

    removeDuplicates(head);
    printf("删除重复节点后的链表：");
    printLinkedList(head);

    return 0;
}

该算法的时间复杂度为O(n^2)，其中n为链表的长度。