Link List

[emanshu, Munish Nayyar]

Hi all,

i am looking for different solutions for the fow:- problems please let
me know if anyone have any idea.

problem 1:- we have link list ( singly link list ), in which some
node( say X node) is pointing to some previous node ( say E) and i want
to search for node which is pointing back to previous nodes.

problem 2:- there is some link list( singlu link list ) and I have
given some intermediate node Pointer ( i dont have access to the Head
of the list). and i want to delete that intermediate node in the list.

PLease if anybody is having any idea, i will really appreciate.

rgrds,
Munish Nayyar

 

[Suman]

Hi all,

i am looking for different solutions for the fow:- problems please let
me know if anyone have any idea.

Strictly speaking, you ought to be asking in
comp.programming.

problem 1:- we have link list ( singly link list ), in which some
node( say X node) is pointing to some previous node ( say E) and i want
to search for node which is pointing back to previous nodes.

Need better description.

problem 2:- there is some link list( singlu link list ) and I have
given some intermediate node Pointer ( i dont have access to the Head
of the list). and i want to delete that intermediate node in the list.

What about something along the lines of the following

1. Say you have pointer to node X, which in turn
points to another node Y.
2. Save a pointer to Y.
3. Copy the contents of Y (including its next link) to
X
4. Delete Y.
Of course, the above is good enough if you don't have any other
constraints!

 

[emanshu, Munish Nayyar]

thanks for your replies.

Strictly speaking, you ought to be asking in
comp.programming.


Need better description.

say wehave link list of nodes like
1-->2-->3-->4-->5--| here node 5 is pointing back to 3 node.
so i want to search
|________| such nodes.

one sol is to keep track of all address and compare while traversing,
if comparison succeed then we have founded the required node.
but this method seems to be inefficient in case linklist of say 2000 or
more nodes.

What about something along the lines of the following

1. Say you have pointer to node X, which in turn
points to another node Y.
2. Save a pointer to Y.
3. Copy the contents of Y (including its next link) to
X
4. Delete Y.
Of course, the above is good enough if you don't have any other
constraints!

yes, ur answer is right but is there any way by which i can make X to
points to Z , if there are X Y and Z three successive nodes and we have
given access Y pointer and Y shud b deleted.

Please let me know if anybody is having any idea!!!

thanks,
Munish Nayyar

 

[Anand]

[ Follow up set to comp.programming ]

thanks for your replies.




say wehave link list of nodes like
1-->2-->3-->4-->5--| here node 5 is pointing back to 3 node.
so i want to search
|________| such nodes.

one sol is to keep track of all address and compare while traversing,
if comparison succeed then we have founded the required node.
but this method seems to be inefficient in case linklist of say 2000 or
more nodes.
Hint: Hare and Tortoise


yes, ur answer is right but is there any way by which i can make X to
points to Z , if there are X Y and Z three successive nodes and we have
given access Y pointer and Y shud b deleted.

Please let me know if anybody is having any idea!!!

thanks,
Munish Nayyar

 

[ptr]

Hi all,
Problem 1 is finding loop in a linked list. To do it simply, have a
flag 'IsVisited' in each node, initially 0.

Node * ptr = head ; // points to start of list
while ( ptr != NULL && ptr ->next->IsVisited == 0 )
{
ptr->IsVisited = 1 ; // mark as visited
ptr = ptr -> next ;
}
At the end, ptr points to the required node.
Ofcourse,there are many faster algorithms to detect loops in linked
lists like Hare&Tortoise method.
For more info, u can notify me.
-------------------------------------------------------------------------
Problem 2
int deleteNode ( Node * delptr )
{
int temp ;
if( delptr==NULL )
return 0;
for ( ; delptr -> next != NULL ; delptr = delptr -> next )
{
temp = delptr -> data ;
delptr -> data = delptr -> next -> data ;
delptr -> next -> data = temp ;
if ( delptr -> next -> next == NULL )
break ;
}
free ( delptr -> next ) ;
delptr -> next = NULL ;
return 1;
}

The node to be deleted is bubbled down to the end of the list and then
deleted.
eg. 1-->2-->3-->4 If u want to delete node 2, then the steps wud be,
Step 1 : 1-->3-->2-->4
Step 2 : 1-->3-->4-->2
At this step, delptr points to 4, so u do free(delptr->next) to free 2
and make delptr->next = NULL to complete the list.