已知非空线性链表l的链结点按结点数据域值非递减链接，请写一算法，删除链表中数据域值相同的多余链结点。

### 回答1：
算法如下：

1. 定义指针p和q，分别指向链表的第一个结点和第二个结点。

2. 循环遍历链表，直到q指向链表的最后一个结点。

3. 如果p结点的数据域值等于q结点的数据域值，则删除q结点，并将q指向下一个结点。

4. 如果p结点的数据域值不等于q结点的数据域值，则将p指向q，q指向下一个结点。

5. 返回链表的头结点。

代码实现如下：

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

### 回答2：
这道题的主要思路就是遍历整个链表，如果出现相同的数据域，就删除后面的那个结点。由于链表中的结点按数据域非递减链接，所以我们只需要比较当前结点与下一个结点的数据域是否相等即可。

具体的算法步骤如下：

1. 首先判断链表是否为空，如果为空则直接返回。

2. 定义两个指针p和q分别指向链表的头结点和第二个结点。

3. 遍历整个链表，如果当前结点的数据域与下一个结点的数据域相等，则删除下一个结点，将p指向第一个相同数据域的结点，q指向p的下一个结点；如果当前结点的数据域与下一个结点的数据域不相等，则将p和q各后移一个结点。

4. 最后返回链表的头结点。

下面是具体的代码实现：

void delete_repeat_nodes(ListNode *head)
{
if (head == nullptr || head->next == nullptr) {
return;
}

ListNode *p = head; // 指向第一个不重复的结点
ListNode *q = head->next; // 指向p的下一个结点

while (q != nullptr) {
if (p->val == q->val) {
p->next = q->next; // 删除q结点
delete q;
q = p->next; // 继续判断后面的结点
} else {
p = p->next;
q = q->next;
}
}
}

这个算法的时间复杂度为O(n)，其中n为链表的长度，因为需要遍历整个链表一次。空间复杂度为O(1)，因为只需要定义几个指针变量用来遍历链表，不需要额外的存储空间。

### 回答3：
要删除链表中数据域值相同的多余链结点，我们可以使用双指针来遍历链表，同时使用一个哈希表来记录已经出现过的数据值。

具体来说，我们可以定义一个指针p和一个指针q，初始时它们都指向链表头结点。然后我们在哈希表中记录下第一个结点的数据域值，即head->val。接着，我们让q指针向后移动一个结点，判断它的数据域值是否出现过。

如果q指向的结点的数据域值出现过，那么我们就将此结点删除，即将p指针的next指向q的下一个结点，并释放q结点的内存空间。否则，我们就在哈希表中记录下q结点的数据域值，并将p指针和q指针同时向后移动一个结点。

当q指针遍历完整个链表之后，我们就可以得到一个没有多余链结点的链表了。

具体算法实现如下：

1. 初始化哈希表和双指针p和q，让它们都指向头结点。

2. 在哈希表中记录下头结点的数据域值。

3. 如果q指针不为NULL，则继续遍历链表。

4. 如果q指向的结点的数据域值出现过，则将此结点删除；否则，在哈希表中记录下q结点的数据域值。

5. 将p指针和q指针同时向后移动一个结点，继续遍历链表。

6. 返回新的链表头结点。

代码实现如下：

struct ListNode* deleteDuplicates(struct ListNode* head) {
if (head == NULL) return NULL;

struct ListNode* p = head; // p指针指向当前节点的前一个节点
struct ListNode* q = head->next; // q指针指向当前节点

unordered_map<int, bool> hash; // 哈希表存储已经出现过的值
hash[head->val] = true;

while (q) {
if (hash[q->val]) {
p->next = q->next;
free(q);
} else {
hash[q->val] = true;
p = q;
}
q = p->next;
}

return head;
}

这个算法的时间复杂度是O(N)，其中N是链表中的结点数。空间复杂度也是O(N)，因为我们需要使用一个哈希表来记录已经出现过的数据值。