In a singly-linked list, or slist, each node points to the "next" node only, e.g., A->B->C->D->E. To reverse, you simply traverse the list, save all the existing references, and make each node point to the "previous" node. For node A, you need to find its address for B to point to.
An easy question – I was once asked as a sequel, what happens if the list contains a loop, since in that case (previous answer) the program would run forever. my answer then was that you’d have to check it by saving all addresses etc.Later I realized that inverting a linked list that has a loop is an undefined problem ( i.e. what IS the inverse of a linked list with a loop?).Furthermore, the program won’t run forever. it will stop ( after O(n)) and return the only reasonable thing which can be defined as the inverse of a linked list with a loop
Avi, let’s say we have a linked list A->B->C->D->A. This is a looped slist. Then isn’t the inverted list just A->D->C->B->A? Since a linked list always starts with some "initial" node, I think it’s possible to check for a terminal condition when you invert it, even if it’s looped.
When you have doubly-linked lists, then you won’t have to invert anything…
ANSWER
In a singly-linked list, or slist, each node points to the "next" node only, e.g., A->B->C->D->E. To reverse, you simply traverse the list, save all the existing references, and make each node point to the "previous" node. For node A, you need to find its address for B to point to.
An easy question – I was once asked as a sequel, what happens if the list contains a loop, since in that case (previous answer) the program would run forever. my answer then was that you’d have to check it by saving all addresses etc.Later I realized that inverting a linked list that has a loop is an undefined problem ( i.e. what IS the inverse of a linked list with a loop?).Furthermore, the program won’t run forever. it will stop ( after O(n)) and return the only reasonable thing which can be defined as the inverse of a linked list with a loop
Avi, let’s say we have a linked list A->B->C->D->A. This is a looped slist. Then isn’t the inverted list just A->D->C->B->A? Since a linked list always starts with some "initial" node, I think it’s possible to check for a terminal condition when you invert it, even if it’s looped.
When you have doubly-linked lists, then you won’t have to invert anything…
-brett
link* reverse(link* start){ if (this->next != start) this->next->reverse(start)->next=this; else this->next->next = this; return this; }