蚌埠北京网站建设,品牌logo,青岛网站定做,目录网站模板LeetCode.203移除链表元素 1.问题描述2.解题思路3.代码 1.问题描述
给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.val val 的节点#xff0c;并返回 新的头节点 。
示例 1#xff1a; 输入#xff1a;head [1,2,6,3,4,5,6], val … LeetCode.203移除链表元素 1.问题描述2.解题思路3.代码 1.问题描述
给你一个链表的头节点 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 500 val 50
2.解题思路
以链表 1 4 2 4 来举例移除元素4。 如果使用CC编程语言的话不要忘了还要从内存中删除这两个移除的节点 清理节点内存之后如图 当然如果使用java python的话就不用手动管理内存了。就算使用C来做leetcode如果移除一个节点之后没有手动在内存中删除这个节点leetcode依然也是可以通过的只不过内存使用的空间大一些而已但建议依然要养成手动清理内存的习惯。
那么上述例子中删除第一个4只要将1的next指针直接指向下下个节点就好了。但这样如果删除的是头结点就不好办了于是两个办法。 直接使用原来的链表来进行删除操作。 其余节点用上述法子便行 头结点移除头结点和移除其他节点的操作是不一样的因为链表的其他节点都是通过前一个节点来移除当前节点而头结点没有前一个节点。 所以只要将头结点向后移动一位就可以这样就从链表中移除了一个头结点。依然别忘将原头结点从内存中删掉。 设置一个虚拟头结点在进行删除操作。 这里来给链表添加一个虚拟头结点为新的头结点此时要移除这个旧头结点元素1。就和移除链表其他节点的方式统一了。最后return 头结点的时候别忘了 return dummyNode-next; 这才是新的头结点
3.代码
C直接使用原来的链表来进行删除操作
#include iostream
using namespace std;struct ListNode {int val;ListNode* next;ListNode(int x): val(x), next(NULL) {}
};class Solution {public:ListNode* removeElements(ListNode* head, int val) {// 删除头结点值等于val的节点//为什么不用if因为若输入为head [1,1,1,1,1]应为一个持续移除的过程所以为while//头结点不能为空如果为空相当于操作空指针了while(head ! NULL head-val val) {//创建了一个临时指针tmp它指向链表的头结点head。//这是为了保存需要被删除的节点以便在将指针从链表中删除时能够释放该节点所占用的内存。ListNode* tmp head;head head-next;delete tmp; }ListNode* cur head;//cur ! NULL 确保当前节点不为空。在删除节点时我们需要更改节点的指针来连接正确的节点//所以我们要确保cur指针不为空避免访问空指针导致程序崩溃。//cur-next ! NULL 确保当前节点的下一个节点不为空。在删除节点时//我们需要访问当前节点的下一个节点的值来进行比较如果下一个节点为空//则没有必要进行比较和删除操作while(cur ! NULL cur - next ! NULL) {if(cur-next-val val) {ListNode* tmp cur-next;cur-next cur-next-next;delete tmp;} else {cur cur-next;}}return head;}
};int main() {ListNode* head new ListNode(1);head-next new ListNode(2);head-next-next new ListNode(6);head-next-next-next new ListNode(3);head-next-next-next-next new ListNode(4);head-next-next-next-next-next new ListNode(5);head-next-next-next-next-next-next new ListNode(6);int val 6;Solution s;ListNode* res s.removeElements(head, val);while (res ! NULL) {cout res-val ;res res-next;}return 0;
}C虚拟头结点
#include iostream
using namespace std;struct ListNode {int val;ListNode* next;ListNode(int x): val(x), next(NULL) {}//构造函数
};class Solution {public:ListNode* removeElements(ListNode* head, int val) {ListNode* dummyHead new ListNode(0);//创建虚拟头节点dummyHead-next head;//虚拟头节点指向头节点//临时指针从虚拟头节点开始遍历如果直接用头结点进行遍历那么头结点所指向的值是一直在改变的最后无法返回了ListNode* cur dummyHead;while(cur-next ! NULL) {if(cur-next-val val) {ListNode* tmp cur-next;//暂存要删除的节点cur-next cur-next-next;//删除节点delete tmp;//释放内存} else {cur cur-next;//指向下一个节点}}head dummyHead-next;//更新头节点 因为旧的head可能已经被删除了delete dummyHead;//释放虚拟头节点内存return head;//返回头节点}
};int main() {ListNode* node1 new ListNode(1);ListNode* node2 new ListNode(2);ListNode* node3 new ListNode(6);ListNode* node4 new ListNode(3);ListNode* node5 new ListNode(4);ListNode* node6 new ListNode(5);ListNode* node7 new ListNode(6);node1-next node2;node2-next node3;node3-next node4;node4-next node5;node5-next node6;node6-next node7;Solution solve;ListNode* newhead solve.removeElements(node1, 6); // 删除值为6的节点while(newhead ! NULL) {cout newhead - val ;newhead newhead - next;}return 0;
}python虚拟头结点
class ListNode:def __init__(self, val, nextNone):self.val valself.next nextclass Solution:def removeElements(self, head: ListNode, val: int) - ListNode:dummyHead ListNode()dummyHead.next headcur dummyHeadwhile cur.next:if cur.next.val val:cur.next cur.next.nextelse:cur cur.nextreturn dummyHead.nexthead ListNode(1)
head.next ListNode(2)
head.next.next ListNode(6)
head.next.next.next ListNode(3)
head.next.next.next.next ListNode(4)
head.next.next.next.next.next ListNode(5)
head.next.next.next.next.next.next ListNode(6)sol Solution()
new_head sol.removeElements(head, 6)cur new_headwhile cur:print(cur.val)cur cur.next
