计算机科学基础leetcode刷题链表
,
Source
Edit
History

203. 移除链表元素

Problem: 203. 移除链表元素

思路

基本的链表删除

脑瘫的错误

遍历链表是while(current->next != nullptr)一开始记不得了

复杂度

  • 时间复杂度:

$O(n)$

  • 空间复杂度:

$O(1)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // 虚拟头节点
        ListNode* dummy = new ListNode(0);dummy->next = head;
        // 找到需要删除的节点
        // 保存要删除的节点之前的节点 pre
        ListNode *pre = dummy,*cur = head;
        while (cur != nullptr) {
            if (cur->val == val) {
                // 断开需要删除的并且将pre连接到其子节点
                pre->next = cur->next;
                delete cur;
                cur = pre->next;
            } else {
                pre = cur;
                cur = cur->next;
            }
        }
        return dummy->next;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
    
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* current = dummyHead;

        while(current->next != nullptr) {
            if(current->next->val == val) {
                ListNode* p = current->next;
                current->next = current->next->next;
                delete p;
            }else{
                current = current->next;
            }
        }

        head = dummyHead->next;
        delete dummyHead;
        return head;
    }
};