Linked List Interesting problem - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

#### Categories

Posts: 28Member
Hi,
In a linked list if the last node is pointing to one of the previous node, rather than pointing to the null. How do I find the last node.

With Regards
Murali

• Posts: 937Member
: Hi,
: In a linked list if the last node is pointing to one of the previous node, rather than pointing to the null. How do I find the last node.
:
: With Regards
: Murali
:

Hi!

If the "last" node is pointing to a previous one, then the links are bad. This happens with a link list and, in my opinion, is one of the bad features of a linked list.

If one or more of the links are bad, you need to recreate them. So you end up having to sort the list, then update all of the links. It's tedious, but it's the only way I know how.

Well, not the only way... You could write a procedure that steps through the list and keeps track of any node that is accessed. then, as you step through the list, if you see a node that's already been accessed, you know that link, or a subsequent one, is bad.

You might be able to fix them up at that point without sorting the whole list. Or just sort the ones that are bad, fix up those links, and continue on.

Linked lists can be fast, but they can be trouble...

[purple]Melissa[/purple]

• Posts: 28Member
Hi,
Got the solution use two pointers okay. With one move one node at a time and with the other move two nodes at a time. Thats the solution. The best solution i guess.

With Regards
Murali

: : Hi,
: : In a linked list if the last node is pointing to one of the previous node, rather than pointing to the null. How do I find the last node.
: :
: : With Regards
: : Murali
: :
:
: Hi!
:
: If the "last" node is pointing to a previous one, then the links are bad. This happens with a link list and, in my opinion, is one of the bad features of a linked list.
:
: If one or more of the links are bad, you need to recreate them. So you end up having to sort the list, then update all of the links. It's tedious, but it's the only way I know how.
:
: Well, not the only way... You could write a procedure that steps through the list and keeps track of any node that is accessed. then, as you step through the list, if you see a node that's already been accessed, you know that link, or a subsequent one, is bad.
:
: You might be able to fix them up at that point without sorting the whole list. Or just sort the ones that are bad, fix up those links, and continue on.
:
: Linked lists can be fast, but they can be trouble...
:
:
: [purple]Melissa[/purple]
:
:

• Posts: 1Member
Hi,
If we get
node->next=node->next->next->next
then node->next
is the last node, while scanning from the start node.

: Hi,
: Got the solution use two pointers okay. With one move one node at a time and with the other move two nodes at a time. Thats the solution. The best solution i guess.
:
: With Regards
: Murali
:
: : : Hi,
: : : In a linked list if the last node is pointing to one of the previous node, rather than pointing to the null. How do I find the last node.
: : :
: : : With Regards
: : : Murali
: : :
: :
: : Hi!
: :
: : If the "last" node is pointing to a previous one, then the links are bad. This happens with a link list and, in my opinion, is one of the bad features of a linked list.
: :
: : If one or more of the links are bad, you need to recreate them. So you end up having to sort the list, then update all of the links. It's tedious, but it's the only way I know how.
: :
: : Well, not the only way... You could write a procedure that steps through the list and keeps track of any node that is accessed. then, as you step through the list, if you see a node that's already been accessed, you know that link, or a subsequent one, is bad.
: :
: : You might be able to fix them up at that point without sorting the whole list. Or just sort the ones that are bad, fix up those links, and continue on.
: :
: : Linked lists can be fast, but they can be trouble...
: :
: :
: : [purple]Melissa[/purple]
: :
: :
:
:

• Posts: 3Member
hi murali,

u can do one thing. keep one more field for flag.initially that will be 0, whenever u encounter new node ,set that flag as 1. if last node pointing to previous node,that can be find out by the flag.

-vinay

Hi,
: In a linked list if the last node is pointing to one of the previous node, rather than pointing to the null. How do I find the last node.
:
: With Regards
: Murali
: