LeetCode 203 - 移除链表元素

题目描述

给你一个链表的头节点 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*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;delete dummyHead;return head;}
};

复杂度分析

• 时间复杂度：O(n)，其中n是链表的长度。需要遍历整个链表一次。
• 空间复杂度：O(1)，只使用了常数级别的额外空间。

总结

=这种方法的时间复杂度和空间复杂度都很低，适用于处理大规模的链表数据。希望本篇博客能给大家提供一些帮助，也欢迎大家多多交流，共同进步！

以上就是对LeetCode203移除链表元素的解题思路、算法实现、复杂度分析和总结，希望对你有所帮助！