帮我写一个链表中删除值相同的多余节点算法

假设链表中节点的值按照从小到大的顺序排列，算法如下：

1. 初始化指针p指向链表头节点。设链表中第一个节点的值为val。
2. 从第二个节点开始遍历整个链表，依次判断每个节点的值是否与val相同。
3. 若节点的值与val相同，则删除该节点，即将当前节点的前驱节点的next指向当前节点的后继节点。
4. 若节点的值与val不同，则更新val为该节点的值，并将p指向该节点。
5. 若链表遍历完毕，则返回链表。

算法的时间复杂度为O(n)，空间复杂度为O(1)。下面是该算法的Python实现代码：

def remove_duplicates(head):
    if head is None:
        return head

    p = head
    val = head.val
    while p.next is not None:
        if p.next.val == val:
            p.next = p.next.next
        else:
            val = p.next.val
            p = p.next

    return head

相关问题

帮我用C语言写一个链表中删除值相同的多余节点算法

以下是一个基于单链表的算法，用于删除值相同的多余节点。具体思路是，首先遍历整个链表，判断每个节点的值是否与前面的节点的值相同。如果相同，则删除当前节点。注意，这种算法只会保留第一个出现的具有相同值的节点，后续的所有节点都将被删除。

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

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

void delete_duplicates(struct Node *head) {
    struct Node *p, *q, *tmp;

    if (!head) {
        return;
    }

    p = head;
    while (p->next) {
        q = p->next;
        if (p->val == q->val) {
            tmp = q;
            p->next = q->next;
            free(tmp);
        } else {
            p = q;
        }
    }
}

int main() {
    struct Node *head, *p1, *p2, *p3, *p4, *p5;

    p1 = (struct Node*) malloc(sizeof(struct Node));
    p2 = (struct Node*) malloc(sizeof(struct Node));
    p3 = (struct Node*) malloc(sizeof(struct Node));
    p4 = (struct Node*) malloc(sizeof(struct Node));
    p5 = (struct Node*) malloc(sizeof(struct Node));

    p1->val = 1;
    p1->next = p2;

    p2->val = 2;
    p2->next = p3;

    p3->val = 2;
    p3->next = p4;

    p4->val = 3;
    p4->next = p5;

    p5->val = 3;
    p5->next = NULL;

    head = p1;

    printf("Before:%d->%d->%d->%d->%d\n", p1->val, p2->val, p3->val, p4->val, p5->val);

    delete_duplicates(head);

    printf("After:%d->%d->%d->%d\n", p1->val, p2->val, p3->val, p4->val);

    free(p1);
    free(p2);
    free(p3);
    free(p4);
    free(p5);

    return 0;
}

输出结果：

Before:1->2->2->3->3
After:1->2->3

链表中删除值相同的多余节点算法

可以使用哈希表（或集合）来记录链表中出现的值，并在遍历链表的同时删除值相同的节点。具体步骤如下：

1. 定义一个哈希表（或集合）来存储链表中出现的节点值。

2. 遍历链表，对于每个节点进行如下操作：

a. 如果该节点值已经在哈希表中出现过，说明该节点值与之前的节点重复了，需要删除该节点。

b. 如果该节点值没有出现过，将该节点值加入哈希表中，继续遍历下一个节点。

3. 遍历完成后，所有重复的节点已经被删除了，链表中仅保留了每个节点值出现的第一个节点。

时间复杂度为 O(n)，其中 n 是链表中节点的个数，空间复杂度为 O(n)。

代码示例（Python）：

def deleteDuplicates(head):
    if not head:
        return None

    # 定义哈希表和双指针
    hashSet = set()
    pre = None
    cur = head

    # 遍历链表
    while cur:
        # 如果该节点值已经在哈希表中出现过，删除该节点
        if cur.val in hashSet:
            pre.next = cur.next
        # 如果该节点值没有出现过，加入哈希表中
        else:
            hashSet.add(cur.val)
            pre = cur

        cur = cur.next

    return head