c++ - 用O(1)时间循环删除链表？

Question

在一本数据结构书上看到了这个问题，是个思考题，没有给答案。网上找了找，似乎也没有。有没有大神提供个思路？

Answer 1

I agree with brayden's statement above. This question has no meaning in terms of data structure and algorithm. It should be that the poster read the question wrongly. The problem is that it takes O(1) time to delete a node in a circular singly linked list. The following is a simple solution to delete a node in a circular singly linked list in O(1) time:
Assume that the node to be deleted is ListNode *toBeDeleted
If deletion is required in O(1) time, traversal cannot be used. Since it is a single-linked list, the previous node of the node cannot be found without traversal, so the conventional linked list deletion method cannot be used.
Since we know the node ListNode *toBeDeleted to be deleted, we can directly get its next node ListNode *pNext. We can overwrite the pNext node with the content of toBeDeleted, then link the node toBeDeleted to the next node of pNext and then delete the pNext node. The following is a simple diagram (assuming i is to be deleted):

The principle is very simple: completely clone the next node, and then delete the next node to achieve the illusion of deleting this node.

Answer 2

I have used similar data structures before, so there is no need to write any memory allocation function. The main implementation ideas are as follows:

1. Apply for N consecutive blocks of memory at the beginning. The content of each block of memory is the tag and linked list node data of whether the block of memory is used.
2. When adding a node, find an unused memory block in continuous memory and mark it as used.
3. This block of memory is marked as unused when the node is released.
4. When deleting the linked list, just release N consecutive blocks of memory.
5. Other problems such as running out of the applied contiguous memory basically have solutions.

But the main problem with this is: if the node contains resources, then the resources will inevitably be leaked.