用单链表保存m个整数,结点的结构为: [data | link]且|data|≤n(n为正整数)。现要求设计一个时间复杂度尽可能高效的算法,对于链表中data的绝对值相等的结点,仅保留第一次出现的结点而删除其余绝对值相等的结点。(1≤m,|n|≤10000)例如,若给定的单链表head如下:
时间: 2024-03-13 07:46:02 浏览: 101
好的,你的问题是关于单链表的算法,我会尽力回答。根据你的要求,我们需要遍历整个链表并记录每个出现的数据,以便删除后续的相同数据。具体的步骤如下:
1.定义一个数组count,用于记录每个数据出现的次数。
2.遍历链表,对于每个结点,将其数据的绝对值作为下标,在count数组中对应位置加1。
3.再次遍历链表,对于每个结点,查找其数据在count数组中对应的值,如果大于1,则说明该数据之前已经出现过,将该结点删除;否则继续遍历下一个结点。
代码实现如下(C++):
```c++
void deleteDuplication(ListNode *head, int n) {
int count[n] = {0};
ListNode *cur = head, *prev = nullptr;
while (cur) {
int index = abs(cur->val);
if (count[index] == 0) {
count[index] = 1;
prev = cur;
} else {
prev->next = cur->next;
delete cur;
}
cur = prev->next;
}
}
```
其中,head为单链表的头结点,n为数据的取值范围,即|n|。
需要注意的是,由于每个结点只能被访问一次,因此时间复杂度为O(m),其中m为链表的长度。
阅读全文
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![-](https://img-home.csdnimg.cn/images/20241226111658.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![doc](https://img-home.csdnimg.cn/images/20241231044833.png)
![cpp](https://img-home.csdnimg.cn/images/20250102104920.png)