赞
踩
链表篇,开始。
记录六:力扣【203移除链表元素】
来源【代码随想录】,总结:
(1)线性结构。内存地址不连续,通过指针指向串联一起。
(2)链表类型:
(3)链表定义(用C++)
//定义节点
struct Listnode{
int data;//数据,int可以换别的,看要放什么data
int* p;//指针,单链表就一个
//int* pred;指前面的指针
//int* succ;指后面的指针
};
C++中struct和class类似,同样可以用成员函数,都是自定义类型。
可以typedef另起一个名字。比如:
typedef struct Listnode{
int data;//数据,int可以换别的,看要放什么data
Listnode* pred;//指前面的指针
Listnode* succ;//指后面的指针
}Node;
Node n1;
n1.data = 5;
(4)链表操作
总结:操作指针。
给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点 。
示例 1:
输入:head = [1,2,6,3,4,5,6], val = 6
输出:[1,2,3,4,5]
示例 2:
输入:head = [], val = 1
输出:[]
示例 3:
输入:head = [7,7,7,7], val = 7
输出:[]
提示:
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50
(1)先看下对于单链表节点的定义。
(2)从头结点循环往下找节点,遇到=val删掉改变指针。
虽然知道链表删除都是操作指针但实现时需要注意方法。
先上代码,通过测试:
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* removed_pred = nullptr; ListNode* removed = nullptr; ListNode* search = nullptr ;//遍历指针 if(head){ while(head->val == val){ removed = head; if(!(head->next)){ head = nullptr; delete removed; return head; } head = head->next; //search = search->next; delete removed; } removed_pred = head; search = head -> next; while(search !=nullptr){ if(search->val == val ){ removed = search; search = search->next; removed_pred->next = search; delete removed; }else{ removed_pred = search; search = search->next; } } return head; }else{ return head; } } };
(1)需要返回头结点:
当头结点=val时,head需要一直后移;当头结点不等于val时,head不需要再移动,只用看后面的节点谁等于val,被删去,所以这里需要一个指针来查找后面元素,此时head固定不再移动。
所以先实现头结点=val,head一直后移: while(head->val == val){ //当head不等于val时,不再循环,开始往后查找,head也就固定不动。 removed = head; //由于考虑到删除节点所在内存,所以用removed指针先指向被删除的节点,等链表指针改动完成后,delete。 head = head->next; //头指针需要后移;(有缺陷) search = search->next; //search是查找指针,初始化为head; delete removed; //把“应该删去的节点”内存释放掉 } 再实现当head固定时,查找节点并删除操作: while(search -> next){ //search指向正在被判断的节点,看它要不要删去;当操作到最后一个节点时,无法进入循环,所以后面要特别处理。 if(search->val == val ){ //判断当前节点等于val removed = search; //removed含义,方便释放节点内存 search = search->next; //search移到下一位 removed_pred->next = search; //跨过待删除的节点,指向下一位。 delete removed; } //判断当前节点不等于val removed_pred = search; // removed_pred指向待删除节点的前一位,需要记下来,改变 removed_pred的指向。 search = search->next; } if(search -> val == val){ //处理最后一个节点 removed_pred->next = nullptr; } return head; //返回链表
(2)注意“-> next”很容易赋值到nullptr(空指针),导致访问空指针的运行错误。
所以还要考虑以下可能:
head指向空,初始传入参数head == nullptr;所以修正一:
在最外层加if(head),如果不为空,开始while操作head;else 直接返回head;
链表只有一个节点,且该节点 = val。所以修正二:
//这两行很容易赋值到nullptr,紧跟着后面while(search -> next)导致访问空指针运行错误。
head = head->next; //头指针需要后移;(有缺陷)
search = search->next;
用例[1,2,1],val=2。进入while(search -> next)后,走到if条件符合进入if逻辑,此时removed_pred=nullptr,又一次操作了空指针。所以修正三。
修正结束:
//通过测试 class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* removed_pred = nullptr; ListNode* removed = nullptr; ListNode* search = nullptr ;//遍历指针 if(head){ while(head->val == val){ removed = head; if(!(head->next)){ head = nullptr; delete removed; return head; } head = head->next; //search = search->next; delete removed; } removed_pred = head; search = head -> next; while(search !=nullptr){ if(search->val == val ){ removed = search; search = search->next; removed_pred->next = search; delete removed; }else{ removed_pred = search; search = search->next; } } return head; }else{ return head; } } };
最终得到提交版本。
(1)解法一:移除头节点和中间节点分开操作。
//发现即使分开操作的思想,我写的也很复杂。重新实现(有错),一写就废 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeElements(ListNode* head, int val) { while((head != nullptr)&&(head->val == val)){ head=head->next; ListNode* tmp = head; //这里出错,先tmp再head=head->next。 delete tmp; } ListNode* cur = head; //while(cur->next != nullptr )//同时判断cur != nullptr while(cur->next != nullptr && cur != nullptr){ //有错 if(cur->next->val == val){ ListNode* tmp = cur->next; cur -> next=cur->next->next; delete tmp; }else{ cur = cur->next; } } return head; } };
注意:
(2)解法:虚拟头节点:统一节点删除操作。
//根据dummy node思想尝试写一遍 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* dummy_node = new ListNode(0,head); ListNode* search = dummy_node; while(search->next != nullptr){ if(search ->next-> val ==val){ ListNode* removed = search->next; search->next = search->next->next; delete removed; }else{ //必须要有else search = search->next; } } delete dummy_node; //dummy_node也要释放。 return dummy_node->next; } };
(1)判断指针空不空,while(search != nullptr)。while(search)是错的。
(2)加一个虚拟头节点,可以统一删除和添加操作。不用区分删除/添加时:头节点还是中间节点。
(欢迎指正,转载标明出处)
我写出下面的逻辑,但是运行时力扣报错:我非法访问,但我找不到地方。显示说search=head处。请问该怎么解决,欢迎留言。
Line 74: Char 28:
=================================================================
==20==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000098 at pc 0x5599d37f919c bp 0x7ffd3cb611f0 sp 0x7ffd3cb611e8
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* removed_pred = nullptr; //ListNode* removed = nullptr; ListNode* search = nullptr ;//遍历指针 while(head != nullptr){ if(head->val == val){ ListNode* removed = head; head = head->next; delete removed; }else{ break; //当head不在等于val,head固定。进入查找删除。 } } search = head; while((search != nullptr) && (search->next != nullptr) ){ removed_pred = search; if(search->val == val ){ ListNode* removed = search; search = search->next; removed_pred->next = search; //如果没有(search->next != nullptr),这里操作空指针。 delete removed; }else{ search = search->next; } } return head; } };
自我回答:
找到问题了:
在if(search->val == val )这里判断的是search,而不是search->next->val。
所以改完之后,也就是学习内容中的解法一:
//测试通过 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* removeElements(ListNode* head, int val) { ListNode* search = nullptr ;//遍历指针 while(head){ if(head->val == val){ ListNode* removed = head; head = head->next; delete removed; }else{ break; //当head不在等于val,head固定。进入查找删除。 } } search = head; while(search != nullptr && search->next != nullptr){ if(search->next->val == val ){ ListNode* removed = search->next; search->next = search->next->next; delete removed; }else{ search = search->next; } } return head; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。