pta链表山东理工大学单链表重复元素删除

### 关于单链表删除重复元素的实现 在处理单链表时，删除重复元素是一个常见的操作。以下是基于山东理工大学PTA练习中的单链表删除重复元素的具体实现方法。 #### 方法描述 为了删除单链表中的重复元素，可以采用遍历的方式逐一比较节点值并移除重复项。具体来说，可以通过两个指针完成此过程：一个用于指向当前正在检查的节点（`current`），另一个用于在其后续部分寻找相同的值（`runner`）。如果找到相同值，则调整指针跳过该节点；如果没有发现匹配值，则继续移动到下一个节点[^1]。 下面分别给出两种不同形式的头结点情况下的代码示例： #### 头节点不存储有效数据的情况 在这种情况下，头节点仅作为一个辅助标记存在，并未实际保存有意义的信息。 ```c #include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node* next; } Node; // 创建新节点函数 Node* create_node(int value) { Node* new_node = (Node*)malloc(sizeof(Node)); new_node->data = value; new_node->next = NULL; return new_node; } void remove_duplicates(Node* head) { if (!head || !head->next) return; // 如果为空或者只有一个节点则无需去重 Node *current = head->next, *prev = head; while(current){ Node *inner = current->next,*temp_prev=current; while(inner){ if(inner->data==current->data){ temp_prev->next=inner->next; free(inner); inner=temp_prev->next; } else{ temp_prev=inner; inner=inner->next; } } prev=current; current=current->next; } } ``` #### 头节点存储有效数据的情况 当头节点本身也包含了有效的数值信息时，算法逻辑基本保持一致，只需注意从第一个真实数据节点开始执行即可。 ```c void remove_duplicates_with_head_data(Node* head) { if(!head||!head->next)return ; Node* current=head; while(current&&current->next){ Node* runner=current; while(runner->next){ if(runner->next->data==current->data){ Node* duplicate=runner->next; runner->next=duplicate->next; free(duplicate); } else{ runner=runner->next; } } current=current->next; } } ``` 以上两段程序展示了如何针对不同的头部定义来编写去除列表中冗余条目的功能[^2]。 #### 测试用例 假设我们有如下输入序列 `1 -> 2 -> 3 -> 2 -> 4 -> -1` ，其中 `-1` 表明结束信号。经过上述任一版本的方法处理后应得到的结果为 `1 -> 2 -> 3 -> 4`. ### 注意事项 - 需要特别关注内存管理，在释放被删掉的节点之前一定要先更新其前驱节点的链接关系。 - 对于极端测试案例比如全是重复数字或者是完全无序的大规模随机数列等情况也要能够正确应对。