c++删除链表重复数字
时间: 2023-10-11 19:12:00 浏览: 58
可以使用双指针法来删除链表中的重复数字。首先将两个指针都指向链表的头部,然后用一个指针p遍历整个链表,另一个指针q指向上一个非重复数字的位置。如果p所指向的数字与q所指向的数字相同,则将p向后移动一个位置;如果不同,则将q向后移动一个位置,并将q所指向的位置替换为p所指向的位置的数字。最后,将q所指向的位置之后的所有节点都删除即可。
代码实现如下:
```
struct ListNode* deleteDuplicates(struct ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
struct ListNode* p = head;
struct ListNode* q = head;
while (p != NULL) {
if (p->val != q->val) {
q->next = p;
q = p;
}
p = p->next;
}
q->next = NULL;
return head;
}
```
时间复杂度为O(n),空间复杂度为O(1)。
相关问题
pta删除链表中的重复数据
这是一个经典的链表操作问题,可以使用双指针来解决。
具体的思路是:使用两个指针p和q,p指向链表的头结点,q指向p的下一个节点。如果p和q的值相等,则将q删除,否则将p和q同时向后移动一个节点。
具体的代码实现可以参考以下示例:
```C++
#include <iostream>
#include <unordered_set>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) {
return NULL;
}
ListNode dummy(0);
dummy.next = head;
ListNode *p = &dummy, *q = head;
while (q != NULL) {
if (p->val == q->val) {
p->next = q->next;
q = q->next;
} else {
p = p->next;
q = q->next;
}
}
return dummy.next;
}
int main() {
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(2);
head->next->next->next = new ListNode(3);
head->next->next->next->next = new ListNode(4);
head->next->next->next->next->next = new ListNode(4);
head->next->next->next->next->next->next = new ListNode(5);
ListNode* result = deleteDuplicates(head);
while (result != NULL) {
cout << result->val << " ";
result = result->next;
}
cout << endl;
return 0;
}
```
此代码的时间复杂度为$O(n)$,其中$n$是链表的长度。
c++智能指针 链表 内存泄漏
智能指针是一种自动管理内存的工具,可以帮助我们避免内存泄漏和悬挂指针等问题。对于链表这种动态数据结构,我们可以使用智能指针来管理节点的内存。
当我们使用智能指针管理链表节点时,需要注意以下几点:
1. 避免循环引用
在链表中,一个节点的指针通常指向下一个节点。如果我们使用普通指针来管理节点内存,可能会出现循环引用的情况,导致内存泄漏。使用智能指针时,需要避免循环引用,可以使用 weak_ptr 来解决。
2. 避免重复删除
当我们使用智能指针管理节点内存时,不需要手动释放内存。如果我们使用 delete 或 free 等函数释放内存,可能会导致重复删除的问题,最终导致程序崩溃。因此,在使用智能指针管理节点内存时,不要手动释放内存。
3. 避免空指针
当链表中的节点被删除后,指向该节点的指针可能会成为空指针。使用空指针操作可能会导致程序崩溃。因此,在使用智能指针时,需要判断指针是否为空,避免空指针操作。
总之,使用智能指针管理链表节点可以帮助我们避免内存泄漏和悬挂指针等问题,提高程序的稳定性和安全性。