实现删除单链表中值相同的多余结点的算法

可以使用双重循环遍历单链表，对于每个结点，再遍历其后续结点，如果有值相同的结点，则将其删除。具体实现如下：

1. 定义两个指针p和q，初始时p指向链表的头结点，q指向p的下一个结点。

2. 循环遍历链表，对于每个结点p，再循环遍历其后续结点，对于每个结点q，如果q的值与p相同，则将q从链表中删除。

3. 删除结点q的方法为：将p的next指针指向q的下一个结点，然后释放q的内存空间。

4. 如果q的值与p不同，则将q指针向后移动一位，继续循环遍历。

5. 当q指针移动到链表的末尾时，将p指针向后移动一位，继续循环遍历。

6. 当p指针移动到链表的末尾时，算法结束。

完整代码如下：

void removeDuplicates(ListNode* head) {
ListNode* p = head;
while (p != nullptr) {
ListNode* q = p->next;
while (q != nullptr) {
if (q->val == p->val) {
p->next = q->next;
delete q;
q = p->next;
} else {
q = q->next;
}
}
p = p->next;
}
}

相关问题

编写一算法删除带头节点的单链表中值相同的多余结点，，即若链表中有多个结点具有相同的数据域，只保留其中一个结点，其余结点均从链表中删去，使得最后得到的链表中的所有结点的数据域都不相同

为了编写这个算法，你可以按照以下步骤设计：

1. 首先，创建两个指针`current`和`previous`，分别指向当前节点和前一个节点。初始化时，`current`设置为头节点，`previous`设置为`null`。

2. 当`current`不为空时，进入循环：
a. 创建一个临时变量`temp`，用于存储`current`的值。
b. 检查`current`的下一个节点(`next`)的值是否与`current`的值相同：
- 如果相同，将`current`的`next`指向前一个节点(`current.next = previous`)，即将当前节点链接到前一个节点，从而删除它。
- 如果不同，将`previous`更新为`current`，继续检查下一个节点。

3. 在每次迭代结束后，`current`会自动向后移动一位，直到遍历完整个链表。

4. 循环结束后，`current`将会是链表的新头节点（如果仍然有相同值的节点），而之前的`previous`就是最后一个需要连接到新头节点的节点。

以下是伪代码表示：

def delete_duplicates(head):
    if not head or not head.next:
        return head
    
    current = head
    previous = None
    
    while current:
        temp = current.value  # 保存当前节点的值
        next_node = current.next
        
        if next_node and next_node.value == temp:
            current.next = previous  # 删除当前节点
        else:
            previous = current  # 更新前一个节点为当前节点
        current = next_node  # 移动到下一个节点

    return current

编写一c语言算法删除带头节点的单链表中值相同的多余结点，，即若链表中有多个结点具有相同的数据域，只保留其中一个结点，其余结点均从链表中删去，使得最后得到的链表中的所有结点的数据域都不相同

在C语言中，要编写一个算法来删除单链表中值相同且仅保留一个的多余节点，我们可以采用迭代或递归的方式。这里我将给出一种迭代的方法：

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

// 定义链表结构体
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 函数声明
Node* deleteDuplicates(Node* head);

// 遍历链表，遇到重复值则跳过非第一个出现的节点
Node* iterateDeleteDuplicates(Node* current, Node* previous) {
    while (current != NULL) {
        if (previous != NULL && previous->data == current->data) { // 如果当前节点值等于前一个节点值
            Node* temp = current; // 保存当前节点
            while (temp->next != NULL && temp->next->data == current->data) { // 跳过所有重复的节点
                temp = temp->next;
            }
            current = temp->next; // 更新current指向下一个非重复节点
            free(temp); // 释放重复节点的内存
        } else {
            previous = current; // 更新前一个节点指针
            current = current->next;
        }
    }
    return head; // 返回处理后的头节点
}

int main() {
    // 初始化示例链表
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 1;
    head->next = (Node*)malloc(sizeof(Node));
    head->next->data = 2;
    head->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->data = 3;
    head->next->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->next->data = 2;
    head->next->next->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->next->next->data = 4;

    head = deleteDuplicates(head);
    // 打印处理后的链表
    Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");

    return 0;
}

// 删除链表中值相同节点的函数实现
Node* deleteDuplicates(Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    return iterateDeleteDuplicates(head, NULL);
}

这个程序首先检查链表是否为空或只有一个元素。然后，`iterateDeleteDuplicates`函数遍历链表，每当遇到重复值时，它会跳过所有后续的重复节点，并在适当的时候释放它们的内存。最后返回处理过的头节点。