Quote:
Originally Posted by sahana
isnt the one by single linked list considered to be the most optimal?
|
The solution given for singly linked list may be optimal for it, but a more optimized solution may exist for doubly linked list.
Quote:
Originally Posted by sahana
may be we can have two pointers that go in opposite directions and if they dont meet means there is a cycle.i dont know where my second pointer ie which is to travel back wards has to point initially because i am not given the number of nodes.
|
We can't have second pointer pointing to the last node of list because we have only head and if the list is corrupt we never reach the last node. Due to same reason we canit count the number of nodes in the list.
Quote:
Originally Posted by sahana
some hint please.
|
The basic property of doubly linked list is that every node has two pointers, one pointing to next node and other pointing to previous node in the list. Having an extra pointer in each node surely increase the space complexity, but that will help in giving more optimized solution to the problem in terms of space complexity.
-Pradeep