写一算法将单链表中值重复的结点删除,使所得的结果表中各结点值均不相同的代码
时间: 2024-03-26 12:38:19 浏览: 104
实现在单链表中删去值相同的多余结点的算法.txt
下面是一种将单链表中值重复的节点删除的算法:
1. 定义变量 prev 和 curr,分别指向链表的前一个节点和当前节点。初始时,prev 指向链表的头节点,curr 指向头节点的下一个节点。
2. 进入循环,遍历链表中的每个节点:
- 如果当前节点的值等于前一个节点的值,则删除当前节点,即让前一个节点的 next 指针指向当前节点的下一个节点,释放当前节点的内存。
- 否则,将 prev 指针指向当前节点,将 curr 指针指向下一个节点。
3. 循环结束后,返回链表的头节点。
下面是算法的具体实现(C++ 代码):
```
ListNode* removeDuplicates(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
ListNode* prev = head;
ListNode* curr = head->next;
while (curr != NULL) {
if (curr->val == prev->val) {
prev->next = curr->next;
delete curr;
curr = prev->next;
} else {
prev = curr;
curr = curr->next;
}
}
return head;
}
```
其中,ListNode 是链表节点的结构体,包含一个值 val 和一个指向下一个节点的指针 next。head 是链表的头节点指针。算法的时间复杂度为 O(n),其中 n 是链表的长度。
阅读全文