文章目录
前言
跟随代码随想录,学习链表相关的算法题目,记录学习过程中的tips。
一、移除链表元素(LeetCode--203)
【1】题目描述:
【2】解决思想:在当前节点判定下一个节点的val是否是目标值,若是则修改当前节点的next指针为下一个节点的next地址。为了使操作更加一致,创建一个头节点辅助操作。
【3】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) {
struct ListNode* headNode = new ListNode(0, head);
struct ListNode* pNode = headNode;
while (pNode->next) {
if (pNode->next->val == val) {
auto tmp = pNode->next;
pNode->next = pNode->next->next;
delete tmp;
} else {
pNode = pNode->next;
}
}
auto tmp = headNode->next;
delete headNode;
return tmp;
}
};
【4】时间复杂度:O(N),只遍历了一遍链表。
【5】空间复杂度:O(1),只是开辟了一个头节点而已。