1. 在一个非递减有序的线性表中，有数值相同的元素存在。若存储方式为单链表，设计算法去掉数值相同的元素，使链表中不再有重复元素，要求算法时间复杂度为 O(N)。例如：算法输入链表为（19，26，26，32，50，62，62，62，89），则输出为（19，26，32，50， 62，89）。作答时，给出必要的分析和说明，以及注释，用类 C 语言写出尽量完整的程序。

以下是基于单链表的算法实现，时间复杂度为O(N)：

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

typedef struct Node {
    int val;
    struct Node* next;
} Node;

void removeDuplicates(Node* head) {
    Node* curr = head;

    while (curr != NULL) {
        Node* runner = curr;

        while (runner->next != NULL) {
            if (runner->next->val == curr->val) {
                Node* temp = runner->next;
                runner->next = runner->next->next;
                free(temp);
            } else {
                runner = runner->next;
            }
        }

        curr = curr->next;
    }
}

void printList(Node* head) {
    Node* curr = head;

    while (curr != NULL) {
        printf("%d ", curr->val);
        curr = curr->next;
    }

    printf("\n");
}

int main() {
    Node* head = NULL;
    Node* tail = NULL;

    // create linked list
    int arr[] = {19, 26, 26, 32, 50, 62, 62, 62, 89};
    int n = sizeof(arr) / sizeof(int);

    for (int i = 0; i < n; i++) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->val = arr[i];
        newNode->next = NULL;

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

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

    removeDuplicates(head);

    printf("List without duplicates: ");
    printList(head);

    return 0;
}

算法思路：

遍历链表中的每个节点，对于每个节点，再遍历其后面的所有节点，如果后面的节点的值等于当前节点的值，则将后面的节点从链表中删除。这种方法的时间复杂度为 O(N^2)。但是题目要求时间复杂度为 O(N)，因此需要用一种更快的方法。

我们可以用一个哈希表来跟踪链表中已经出现的值。具体来说，我们遍历链表，如果当前节点的值已经在哈希表中出现过了，则将该节点从链表中删除；否则，将该值加入哈希表中。这种方法的时间复杂度为 O(N)，但需要使用额外的空间来存储哈希表。

以上代码实现了第一种思路，即遍历链表中的每个节点，删除其后面所有值相同的节点。