用ps做网站,哪个网站有做兼职的,网站开发属于哪个部门,怎么编写自己的网站如果您是第一次看我写的博客#xff0c;可以给我点个赞并关注我吗#xff0c;我会持续分享更多有意思的干货。 文章目录1 题目2 思路3 代码4 小结1 题目
Leetcode203 移除链表元素
给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.val … 如果您是第一次看我写的博客可以给我点个赞并关注我吗我会持续分享更多有意思的干货。 文章目录1 题目2 思路3 代码4 小结1 题目
Leetcode203 移除链表元素
给你一个链表的头节点 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 思路 一开始做这道题我是直接上来就做的但是出现一个问题原文是不带头结点的单链表这就导致可能出现两种情况一种是链表中每个元素都删除删到后面什么都没有了头指针指向NULL且链表中如果只剩下一个结点我们是要做if判断因为删除链表中的最后一个结点是一种特殊情况。
还有一种情况是如果是链表本身什么都没有这种情况也很难受。
对此我们可以采用补头结点的方式。也就是说我们可以指定一个虚拟头结点然后补在原始链表的最前面这样上面两种情况都可以避免。为什么 避免的原因是如果链表中不带头结点的情况下删除最后一个结点是要做特殊情况处理而带头结点的话就不需要因为删除一个结点通常是采用一个前置指针加上一个删除结点指针进行操作而前置指针可以处在虚拟头结点上。
如果是链表本身什么都没有那循环就不必开始。
做完这些之后根据题意要求我们要返回新的头结点。对于题意来说它要的单链表是不带头结点的所以当我们补上一个虚拟头结点后我们要返回的自然是虚拟头结点的后面一个结点的指针。
好了说了这么多开始写代码了
3 代码
/*** 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 *dummyHead new ListNode;//将虚拟头结点接入链表dummyHead-val 0;dummyHead-next head;ListNode * pre dummyHead;while(pre-next ! NULL){if(pre-next-val val){ListNode * temp dummyHead;temp pre-next;pre-next temp-next;delete(temp);}elsepre pre-next;}return dummyHead-next;}
};4 小结
时间复杂度O(n)其中 n是链表的长度。需要遍历链表一次。空间复杂度O(1)。
这道题的巧妙之处在于添加头结点来避免过多地判断特殊情况由此在其他的题目中我们也可以迁移地去学习。当然本题求解采用的是迭代的方式如果喜欢用递归的同学也可以采用递归来处理这道题。
