CareerCup

No never, there exist a loop in a doubly linked list

yes they can have loops, we can find it by taking two pointers and varying the frequency by which we increase them, and if at point of time they point to same node it shows there is a loop.

Unlike single circular LL: a->b->c->a, if there is a loop in double linked list, it may be two cases:
1) a<->b<->c->a, where the c->a is the problem. So it is only the matter of finding a link where the target does not link back. EASY.

2) a<->b<->c<->a, this case you can use the method (fast and slow pointers) above to detect. Or, you can use two pointers traveling on opposite direction.
Where to break the loop? You will have to ask the interviewer for clarification, as any node can be considered as the head.

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.