Question:
Can there exist a loop in a doubly linked list? if so how will you remove it?


maybe an answer:


there can be two types of loops in doubly linked list, which can be fixed using special properties of doubly link list.
1. only next pointer of a node points back to some node in the list. All prev pointer points to right nodes.
2. next pointer of a node points back to some node in the list. ONE of the prev pointer too points to the wrong node.
Please note that more than one next pointer can't point to wrong node to maintain continuity of the list also if more than one prev node points to wrong node , we 'll have to solve this problem by first fixing loop in next pointers like single link list and then fix all the prev. pointers.
simple check (node->next->prev ==node ) while traversing the list can give us if some thing wrong but which one prev pointer in node->next or next pointer in node is incorrectly filled we have to check.
if prev points to wrong node it either point to node we already traversed or points ahead in the llist. if it points ahead in the list it will form a loop in prev pointers.
So we should first check whether prev pointer form a loop using slower and faster pointers. if there is a loop, correct the prev pointer.
if it's not a loop traverse along the prev pointer to reach the start of the list if we maintain a counter we can see if perv pointer points to an earlier node of the list or it's the next pointer in node which has the wrong value (case 1). Fix the node accordingly Once prev node is fixed only case 1 is left to fix. we can than go on and find incorrect next node with our condition and fix it immediately as there can't be more than one wrong perv pointers.
now if more than one prev pointers are incorrect we can't be sure if it form a loop if prev points ahead in the list so we can't make sure which pointer next or prev is incorrect. So we can't fix the problem using doubly link list properties.

(Continued on next question...)

Other Interview Questions

• Imagine you have a hard disk with blocks of memory 1..n.......
• Write a function which finds a substring in a string
• Give examples of cases where you would prefer to pass objects/variables by reference instead of value?
• Write a function that takes in two rectangles and returns true if the overlap and false if they do not.Find one missing card from deck of 51 card
• SCVMM - Or Server tools - whatever found that the person .......
• Two unsorted linked lists are given. Find the union......
• Find first repeated substring in a given input string. ......
• Can there exist a loop in a doubly linked list? if so how will you remove it?
• Write a function that takes an array of five integers .....
• Difference between c++ and c#
• More...