个人网站开发的感想,石家庄网页定制开发,东莞 网站建设 保健品,wordpress词 条主题题目描述
给你一个链表的头节点 head 和一个整数 val #xff0c;请你删除链表中所有满足 Node.val val 的节点#xff0c;并返回 新的头节点 。 解题思路
创建一个虚拟头节点dummyHead#xff0c;并将其next指向给定的头节点head#xff0c;这样可以避免处理头节点的特…题目描述
给你一个链表的头节点 head 和一个整数 val 请你删除链表中所有满足 Node.val val 的节点并返回 新的头节点 。 解题思路
创建一个虚拟头节点dummyHead并将其next指向给定的头节点head这样可以避免处理头节点的特殊情况。使用指针cur来遍历链表当cur的下一个节点不为空时进行如下操作 1.如果cur的下一个节点的值等于给定的数值val则将其下一个节点即要移除的节点保存在临时指针tmp中然后将cur的next指针指向下下个节点同时删除tmp指向的节点完成移除操作。 2.如果cur的下一个节点的值不等于给定的数值val则将cur指针指向下一个节点即保持链表的连续性。 3.最后将head指向dummyHead的下一个节点即新的头节点然后删除dummyHead节点释放内存最终返回新的头节点。
算法实现
C实现
/*** 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*dummyHeadnew ListNode(0);dummyHead-nexthead;ListNode*curdummyHead;while(cur-next!NULL){if(cur-next-valval){ListNode*tmpcur-next;cur-nextcur-next-next;delete tmp;}else{curcur-next;}}headdummyHead-next;delete dummyHead;return head;}
};
复杂度分析
时间复杂度O(n)其中n是链表的长度。需要遍历整个链表一次。空间复杂度O(1)只使用了常数级别的额外空间。
总结
这种方法的时间复杂度和空间复杂度都很低适用于处理大规模的链表数据。希望本篇博客能给大家提供一些帮助也欢迎大家多多交流共同进步
以上就是对LeetCode203移除链表元素的解题思路、算法实现、复杂度分析和总结希望对你有所帮助
