算法框架
void remove_6(Node *head,Node *L) {
if (head == NULL || head->next == NULL) {
// 如果链表为空或只有一个节点,无需删除操作,直接返回
return;
}
Node *p = head->next;
// 创建哈希表
int temp[100000] = {0};
Node *prev = head; // 用于跟踪当前节点的前一个节点
while (p) {
int K = abs(p->data);
if (temp[K] == 1) {
addToAnotherList(p, L);
prev->next = p->next; // 删除当前节点
delete p;
p = prev->next; // 继续下一个节点
} else {
temp[K] = 1;
prev = p;
p = p->next;
}
}
}
算法思路:
创建两个专属的删除函数以及添加函数,其功能分别为将将当前指针所指向的节点删除并将当前指针所指向的节点插入到另一个链表的尾部,所传入的参数分别为所原始单链表的头节点指针以及当前指针,以及当前指针以及将删除元素存储的目标链表指针。
所会遇到的问题:
问题1:
当前指针在删除之后会出现可能不再指向有效的链表头而导致的哈希数组下标越界问题也就是我们常说的segmentation fault
问题2:
在insert函数以及del函数中会出现的传进去的待存储链表头节点next指针没有指向问题
解决办法
问题一:
使用一个前驱节点记录p(记录当前位置的指针)的位置,在删除完p节点的时候,使用前驱节点重新定位
问题二:
在创建待存储链表的时候将next指针指向NULL