for linked we always have only head
On Thu, Dec 8, 2011 at 11:40 PM, sayan nayak sayanna...@gmail.com wrote:
@Himanshu: If I follow ur algo..then I have to remove the loop..Otherwise
there will not be any head for the reversed linked-list.
If u wanna say..First remove the loop,make it a
Can we detect if a loop is present in Linked List if only head ptr is given
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
Ofcourse we can..
U knw the head address now U start visit the list what is the big deal??
Jst u gotto create two pointer say fast and slow with two diff speed of
action..
On Thu, Dec 8, 2011 at 6:27 PM, Ankur Garg ankurga...@gmail.com wrote:
Can we detect if a loop is present in Linked
U cant create any new ptrs .Just use this ptr :)
On Thu, Dec 8, 2011 at 6:30 PM, Prem Krishna Chettri hprem...@gmail.comwrote:
Ofcourse we can..
U knw the head address now U start visit the list what is the big
deal?? Jst u gotto create two pointer say fast and slow with two diff speed
It's possible if u modify the definition of the node itself.
add one variable ..let's say:IsVisited for every node. initialized to
false.And while traversing the list
make it true.
Now traverse it and check whether head-next is true or false.
If true return .
But in this process original Linked
slight correction :head-next-IsVisited is true or false
On Thu, Dec 8, 2011 at 6:42 PM, sayan nayak sayanna...@gmail.com wrote:
It's possible if u modify the definition of the node itself.
add one variable ..let's say:IsVisited for every node. initialized to
false.And while traversing the
If you allow storing an extra bit with every node (to mark whether a node
has been visited), you can do it with just one pointer. But that's less
space efficient (O(n)) than using two pointers of varying speeds.
On Thu, Dec 8, 2011 at 9:04 AM, Ankur Garg ankurga...@gmail.com wrote:
U cant
take two pointer
run first with one speed and another with two until they meet,
now take a first pointer and assign with head of list .
now move again both same speed (only one forward at a time )
now as they meet at point that will be your starting pointer of loop.
On 12/8/11, Deepak Nettem
if u cant create new ptrsthen i think horse and tortoise strategy will
fail.
then you can only modify the linked lists to detect the loop.
one other strategy could be to reverse the linked list.after reversing
the linked list, if you arrive at the head itself then the list
@Himanshu: How can u reverse a linked list which has only the
beginning(head) but no tail...
And even if I consider that by some means u have reversed it..then also
there is no guarantee that u reach the head..
Because the LinkedList is not necessarily circular..a circular Linkedlist
and a
@sayan: take a singley linked list (not circular) with a loop in ittry
to reverse it.you will get why i gave this algo...it can be
reversedand it always ends up landing at original head of list if it
contains a loop
give it a try...
On Thu, Dec 8, 2011 at 11:30 PM, sayan nayak
@Himanshu: If I follow ur algo..then I have to remove the loop..Otherwise
there will not be any head for the reversed linked-list.
If u wanna say..First remove the loop,make it a normal linked list,reverse
it.and then again loop it remembering the
previous link..then it's possible.But the Time
I appreciate everyone effort here but guy's the question here is to Not Use
any More pointer (Rather Space Utilization)..
I Donno , if there is a any way to detect without any further space..
Else my First Solution works neatly...
Br,
On Thu, Dec 8, 2011 at 11:34 PM, himanshu kansal
13 matches
Mail list logo
