文章目录
前言
一、移除链表元素(LeetCode--203)
前言
跟随代码随想录,学习链表相关的算法题目,记录学习过程中的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),只是开辟了一个头节点而已。