[BUG] - Cannot free memory. 3217. Delete Nodes From Linked List Present in Array

[Wangch29]

LeetCode Username

Ikun

Problem Number, Title, and Link

3217. Delete Nodes From Linked List Present in Array https://leetcode.com/problems/delete-nodes-from-linked-list-present-in-array

Bug Category

Incorrect test case (Output of test case is incorrect as per the problem statement)

Bug Description

In C++, when you want to delete a node, you should "delete node". However, the testcases disallow us to delete nodes, which will lead to memory leaking. When I try to delete a node , the testcases will cause runtime error, which is unreasonable.

Language Used for Code

C++

Code used for Submit/Run operation

class Solution {
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head) {
        std::unordered_set<int> set(nums.begin(), nums.end());

        ListNode sentinel;
        sentinel.next = head;
        auto cur = &sentinel;

        while (cur->next) {
            if (set.count(cur->next->val)) {
                auto tmp = cur->next;
                cur->next = tmp->next;
                // delete tmp;
            } else {
                cur = cur->next;
            }
        }

        return sentinel.next;
    }
};

Expected behavior

I can delete a node without causing runtime error.

Screenshots

No response

Additional context

No response

[exalate-issue-sync[bot]]

LeetCode Support commented: Thank you for reaching out regarding the potential issue with handling memory management in C++ for this problem. We understand it must be frustrating when operations like "delete" trigger unforeseen errors. The LeetCode platform uses specific testing environments that might have particular constraints or expectations that aren't immediately apparent.

To better assist you, could you provide further details on the specific runtime error message you encountered and any modifications or workarounds you've attempted so far? Additionally, if there's any official documentation or problem constraints that mention memory handling specifics, please refer them. Clarifying these points will enable us to investigate if the issue is inherent to the question setup or if specific guidelines need to be followed for successful code execution.

Feel free to review the problem constraints and our guidelines on how linked list operations should be managed within our test framework. We're here to support you as you seek a solution.

LeetCode Support Team

[Wangch29]

If I uncomment the "// delete tmp;" in the previous code, it will cause the following runtime error. When I comment the "delete tmp;", it can pass the tests, which will cause memory leak because I didn't free the deleted nodes.

Line 73: Char 9:

==22==ERROR: AddressSanitizer: heap-use-after-free on address 0x5020000000f8 at pc 0x564a7206a3a1 bp 0x7ffe3ee6d400 sp 0x7ffe3ee6d3f8 READ of size 8 at 0x5020000000f8 thread T0

0 0x564a7206a3a0 in ListNodeUtils::freeList(ListNode*&) (solution+0x1ab3a0)

#1 0x564a72042f36 in main solution.cpp:73:9
#2 0x7f290da08d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: 490fef8403240c91833978d494d39e537409b92e)
#3 0x7f290da08e3f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x29e3f) (BuildId: 490fef8403240c91833978d494d39e537409b92e)
#4 0x564a71f71e44 in _start (solution+0xb2e44)

0x5020000000f8 is located 8 bytes inside of 16-byte region [0x5020000000f0,0x502000000100) freed by thread T0 here:

0 0x564a72040f3d in operator delete(void*) /root/llvm-project/compiler-rt/lib/asan/asan_new_delete.cpp:152:3

#1 0x564a72043933 in Solution::modifiedList(std::vector<int, std::allocator<int>>&, ListNode*) solution.cpp:73:17
#2 0x564a72042e88 in __helper__ solution.cpp:73:34
#3 0x564a72042e88 in main solution.cpp:73:46
#4 0x7f290da08d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: 490fef8403240c91833978d494d39e537409b92e)

previously allocated by thread T0 here:

0 0x564a720406dd in operator new(unsigned long) /root/llvm-project/compiler-rt/lib/asan/asan_new_delete.cpp:95:3

#1 0x564a7205f379 in ListNode* _Deserializer_::deserialize<ListNode*>(rapidjson::GenericValue<rapidjson::UTF8<char>, rapidjson::MemoryPoolAllocator<rapidjson::CrtAllocator>>&, ListNode**) (solution+0x1a0379)
#2 0x564a72062503 in ListNode* _Deserializer_::deserialize<ListNode*>(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char>> const&) (solution+0x1a3503)
#3 0x564a72042dd8 in main solution.cpp:73:35
#4 0x7f290da08d8f  (/lib/x86_64-linux-gnu/libc.so.6+0x29d8f) (BuildId: 490fef8403240c91833978d494d39e537409b92e)

SUMMARY: AddressSanitizer: heap-use-after-free (solution+0x1ab3a0) in ListNodeUtils::freeList(ListNode*&) Shadow bytes around the buggy address: 0x501ffffffe00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x501ffffffe80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x501fffffff00: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x501fffffff80: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 0x502000000000: fa fa fd fa fa fa fd fa fa fa fd fa fa fa fd fa =>0x502000000080: fa fa 00 00 fa fa fd fa fa fa fd fa fa fa fd[fd] 0x502000000100: fa fa fd fd fa fa fd fd fa fa 00 00 fa fa 00 00 0x502000000180: fa fa fd fd fa fa fd fd fa fa fd fd fa fa fd fd 0x502000000200: fa fa fd fd fa fa fa fa fa fa fa fa fa fa fa fa 0x502000000280: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa 0x502000000300: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa Shadow byte legend (one shadow byte represents 8 application bytes): Addressable: 00 Partially addressable: 01 02 03 04 05 06 07 Heap left redzone: fa Freed heap region: fd Stack left redzone: f1 Stack mid redzone: f2 Stack right redzone: f3 Stack after return: f5 Stack use after scope: f8 Global redzone: f9 Global init order: f6 Poisoned by user: f7 Container overflow: fc Array cookie: ac Intra object redzone: bb ASan internal: fe Left alloca redzone: ca Right alloca redzone: cb ==22==ABORTING

[exalate-issue-sync[bot]]

LeetCode Support commented: Hello,

Your reported issue has been relayed to our team for thorough investigation. We appreciate your patience as we work to address and resolve this matter. We will reach out to you when we have updates regarding the issue.

If you have any further questions or concerns in the meantime, please feel free to let us know.

Best regards, LeetCode Support Team