【算法】代码随想录之链表（更新中）

文章目录

前言

一、移除链表元素（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)，只是开辟了一个头节点而已。