Microsoft Interview Question Software Engineer in Tests
0of 0 votesHow to completely delete a linked list with circle?
The suggested solution will not work because *next will point to a node that was already deleted. after that the program will try to access unallocated memory and wonderful things will happen. This is exactly what this question is trying to check.
To solve easily in O(N) but with a large memory overhead, you can store each deleted node's address in a hash table and check that you are not trying to move to a deleted node. this solution is probably not acceptable.
a better solution would be to go over the list and modify the data of each node to an invalid value (a value that we know was not on the original list). we can locate the circle by finding the first node where next.data == invalid. then we cut the link from that node (so now we no longer a node that is pointed to by 2 other nodes) and delete the list as usual. if there is no predefined invalid data we can make one more pass on the list and find the largest value in it. add 1, and that's our invalid data.
I am pretty sure there is a smarter solution to this, but you can't really beat the O(N).
Do you think following code makes "*next will point to a node that was already deleted."? NO!!!
while(deleteMe)
{
Node *next=deleteMe->next;
delete deleteMe;
deleteMe=next;
}
This can be done in a single pass. Store the starting node in a variable and start deleting from next node. If you find you have reached the starting pointer, just delete this pointer.
First, find the start point of circle(this has been discussed many times in careercup);
Second, delete the nodes of linked list until it reach the previous node of start point of circle;
Third, delete the circle from the next node of start point of circle to the start point of circle.
so everybody knows the algorithm that takes two pointers to find whether a LL contains circle, right?
Just simple modification, when you find the position where two pointers collide, you start deleting the circle,eventually the circle between a single node whose next is itself. So when you only have one single node in a circle, just set its next = NULL.
Then start from beginning,delete the normal LL.
No extra memory cost except two pointers which i think is the min for such kind of circled LL prob. Time is also optimized, I think.
Can MS give me an interview?
The last node in normal LL is not necessarily pointing to the last node in circle,right?
A simple solution wud be, start with a node, say the first, store its data part in a temp variable. now start deleting the nodes, as u move to each node, check if its next pointer points to the data in temp. If it does, then it s the last node. Delete it and you're done. so at each node u get one exrta comparison, but the time complexity wud still remain O(2n)=O(n). space complexity wud be the same since ur using just the one extra temp variable.
Is it specific for a single linked list? with double linked list you can have two circular regions. Any idea how to tackle that?
After deleting the node one can put NULL into pointers.And before deleting any pointer check whether it is pointing to NULL or some memory location.So in that case if by mistake one delete NULL too that wont corrupt the memory.
Comments please??
I guess my idea is to break the loop and then delete the list.To break the loop you have to detect the loop.
Have two pointers P1 & P2 pointing to the head of the linked list,now use the hare and tortoise approach where in one pointer would travel twice as fast as the other.That is P2 moves two times faster than P1.At the position say n, where P1 and P2 point to the same node,leave one of the pointers at the position 'n' and make the other pointer point back again to the head.
Let us say, P1 now points to the head and P2 to 'n'.Now increment both pointers one node at a time only if P1->next !=P2->next.At the point where P1->next==P2->next,break the loop.That is set P2->next to Null.
Now that the loop is removed,you can follow the normal process of deleting the linked list.
Example: 0->1->2->3->4->5->6->7->8->9->10->11->3 head is at '0'
When P1 moves one node at a time and P2 moves two nodes at a time at the node 9 we will find both P1and P2 are pointing to 9.Lets mark node 9 as 'n'.
Now keeping P2 at 'n' and P1 back to head (that is node 0).Now move P1 and P2 one node at a time.When P1 points to node 2 and P2 points to node 11 break the loop,as P1->next and P2->next would be node 3.
Set P2->next that is node 11 ->next to Null.Now delete the linked list as usual.
Will it work for 0-1-2-3-4-1?
According to the algo,
step1: P1 and P2 both converge at 1.
step2: make P1 point to 0 (head) and P2 point to 1 (n).
step3: Loop until P1-next != P2->next
listing the iterations
(P1, p1-next, p2, p2-next)
(0, 1, 1, 2)
(1, 2, 2, 3) *
(2, 3, 3, 4)
(3, 4, 4, 1)
(4, 1, 1, 2)
(1, 2, 2, 3) *
now that's an infinite loop. Need a better logic to find the node to which the back edge points to.
@amused, there is a correction in what you wrote,the point of convergence is node 4 not 1.Here is the working.
Given list 0->1->2->3->4->1.Initially both P1 & P2 are at node 0.The table below gives the positions of P1 & P2 while using the Hare & Tortoise approach.
P1 P2
0 0 initial
1 2
2 4
3 2
4 4 point of convergence call it n.
Step 2, now P1 is moved back to head that is node 0 and P2 points at node 4.Now move both pointers one node at a time,until we P1->next==P2->next.
Here we see that P1-> next is node 1 and P2-> next is also node 1,hence we break the loop here by setting P2->next to null.The list would then be 0->1->2->3->4->null.So this is a singly linked list and you can now do the normal deletion.
Doesn't work for a circular list, if 4->0 instead of 4->1. Should instead find the length of the loop. To do this, instead of returning P1 to the head, make P1 traverse the loop again until it reaches P2 to find the length N. Then reset P1 and P2 to the head. Let P1 travel N-1 nodes then allow P2 to start to traverse along with it from the head. Traverse until P2->next == P1. Now you can set P2->next == NULL.
//Deletes list whether circle present or not
void DeleteListWithCircle(Node * head){
int circleRefCnt = 0;
Node * curr = head, nextNode = NULL;
Node * circleStartNode = getCircleStart(Node * head);
while(curr) {
if(curr == circleStartNode && ++circleRefCnt == 2) {
break;
}
nextNode = curr->next;
free(curr);
curr = nextNode;
}
}
Node * getCircleStart(Node * head) {
Node * ptr1 = head, * ptr2 = head;
if(!head) return NULL;
do {
if(!ptr2 || ptr2->next) return NULL;
ptr1 = ptr1->next;
ptr2 = ptr2->next->next;
} while(ptr1 != ptr2)
//now ptr1 == ptr2
ptr2 = head;
while(ptr1 != ptr2) {
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
//now ptr1 is start of circle
return ptr1;
}
this code should work fine
while(deleteMe!=null)
{
Node *next=deleteMe->next;
delete deleteMe;
deleteMe=next;
}
Can anyone explain why this won't work. Regarding deleteMe pointer getting null, we're already checking that case in the first statement... any thoughts?
Sorry but this won't work and for admittedly a subtle reason. When you delete a node, you can't assume anything about what gets stored in the node's former location. Even if you explicitly set null for the deleted node (which you didn't but I'm guessing you meant to), something else could come along and overwrite it. I say this is "subtle" not because it's hard to understand but because in a realistic situation your code would probably work 99% of the time if the deletion process does not take a long time. However, as explained, it is conceptually wrong to depend on the contents of a freed memory location.
The following code works. I tested it out. The logic is that just go ahead and delete the linked list. When there is a cycle the code throws a exception at the last node. Simply catch the exception and exit gently by making head to NULL. But please advice me if can suggest such a solution. Or is it a programming sin to depend on exceptions in your code.
void LinkedList::deleteList() {
if (head == NULL) return;
node * temp = head;
while(head!=NULL) {
try {
temp = head;
head= head->next;
std::cout<<"\ndeleting "<<temp->data;
delete temp;
}catch(...) {
head = NULL;
}
}
}
First you should ask if this is the likely intent of the problem. That aside, you should ask if an exception will necessarily be thrown. I answered someone else about assuming the contents of freed memory. Basically, you cannot assume anything about freed memory; something else could come along and overwrite your null with some legit pointer to some other data structure. Now what happens? Your deletion process come along and sees that pointer and goes ahead and deletes that data structure (without raising an exception of course). Then depending on what that structure was supposed to do, you could be royally screwed. As I also explained before, your code will likely work 99% of the time, but it is conceptually incorrect.
I think I should reply to your other question about whether it is bad to rely on exceptions in this way ... in general. In my experience, it seems to depend on programming philosophy. Coming from C++, I used to think that this was a bad thing, and I seem to recall people being admonished for using exceptions this way. Then I encountered Java and Python, where this was ok. In fact, there is even a name for this approach: Easier to ask for forgiveness later. This means that instead of trying to be careful and consider all possibilities before doing something, just go ahead and do the thing but catch any error that comes up. The idea is that it simplifies the code. The counter-principle to this, where you check everything first, is called: Look before you leap. My sense is that there is more widespread acceptance of the first principle these days. You should probably look up discussions of these principles and learn about the pros and cons of each; it will certainly make you a more aware developer.
You can just delete the linked list without considering whether it is with circle or not. There is no difference.
- Anonymous October 07, 2009Void deleteList(Node **head){
Node *deleteMe=*head;
while(deleteMe)
{
Node *next=deleteMe->next;
delete deleteMe;
deleteMe=next;
}
*head=NULL;
}