删除单链表中相同的元素

要删除单链表中相同的元素，可以使用双指针遍历单链表，遇到相同元素则删除其中一个。具体的实现过程如下：

1. 定义两个指针p和q，初始时都指向单链表的头节点head。
2. 遍历单链表，当p不为空时，执行以下操作：
- 如果p的值与q的值相同，则删除p节点（即将q的next指向p的下一个节点），并将p指向下一个节点；
- 如果p的值与q的值不同，则将p和q同时向后移动一个节点。
3. 返回删除相同元素后的单链表。

以下是Python代码实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteDuplicates(head: ListNode) -> ListNode:
    if not head:
        return head

    p = q = head
    while p:
        if p.val == q.val:
            q.next = p.next
        else:
            q = p
        p = p.next

    return head

相关问题

用C语言设计算法，删除单链表中相同的元素

1. 定义一个结构体来表示单链表的节点，包含一个数据域和一个指向下一个节点的指针：

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

2. 实现删除相同元素的算法，具体步骤如下：

（1）定义一个指针p指向头节点，一个指针q指向p的下一个节点；

（2）循环遍历单链表，直到p指向尾节点为止；

（3）如果p节点的值和q节点的值相同，就将q节点从链表中删除，即令p的next指向q的next，释放q节点的内存空间；

（4）如果p节点的值和q节点的值不同，就将指针p和q都向后移动一个节点；

（5）重复执行步骤（3）和（4），直到p指向尾节点为止。

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

3. 完整代码如下：

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

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

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

int main() {
    struct ListNode* node1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* node2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* node3 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* node4 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* node5 = (struct ListNode*)malloc(sizeof(struct ListNode));
    node1->val = 1;
    node2->val = 2;
    node3->val = 2;
    node4->val = 3;
    node5->val = 3;
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = NULL;
    printf("Before deleting duplicates: ");
    struct ListNode* p = node1;
    while (p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
    deleteDuplicates(node1);
    printf("After deleting duplicates: ");
    p = node1;
    while (p != NULL) {
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
    free(node1);
    free(node2);
    free(node3);
    free(node4);
    free(node5);
    return 0;
}

将单链表中重复元素删除

可以通过遍历单链表，使用一个哈希表记录每个元素出现的次数，如果出现次数大于1，则删除该节点。具体实现如下：

1. 定义一个哈希表，记录每个元素出现的次数。
2. 定义两个指针，一个指向当前节点，一个指向前一个节点。
3. 遍历单链表，当遇到重复元素时，删除当前节点。
4. 更新当前节点和前一个节点指针。

以下是示例代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def delete_duplicates(head: ListNode) -> ListNode:
    if head is None:
        return None

    # 定义哈希表和指针
    hash_table = {}
    curr = head
    prev = None

    while curr:
        # 如果当前元素出现次数大于1，删除该节点
        if curr.val in hash_table and hash_table[curr.val] > 0:
            if prev is None:
                head = curr.next
            else:
                prev.next = curr.next
            curr = curr.next
        else:
            # 更新哈希表和指针
            hash_table[curr.val] = 1
            prev = curr
            curr = curr.next

    return head

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。