• 01-28-2002
ss3x
Hey fellas:

Question, i wrote a program three different ways, i'm diong it the last way now to get O(1) extra space from printing a linked list out backwards.. it has to be singly linked and printed in reverse order without recursion.

i want to revers the linking on my nodes, but have no idea of where to start! any info/web links are appreciated.

thanks
• 01-29-2002
Unregistered
>O(1) extra space
eh?

assuming you have a pointer to the head node, you need to do something like this:

[list = 1][*] unlink head node and set it to a temp node[*] set head node to another temp node (there are two temp nodes)[*] link the first temp node to the tail of the secode temp node[*] assign the first temp node the value of the second temp node[*] repeat steps 2 - 5 until there are no more nodes in your original list[*] set the head node pointer in your original list to the value of the first temp node[/list = 1]
• 01-29-2002
*ClownPimp*
Lets try this again...

>O(1) extra space
eh?

assuming you have a pointer to the head node, you need to do something like this:

[list=1] [*] unlink head node and set it to a temp node [*] set head node to another temp node (there are two temp nodes) [*] link the first temp node to the tail of the secode temp node [*] assign the first temp node the value of the second temp node [*] repeat steps 2 - 5 until there are no more nodes in your original list [*] set the head node pointer in your original list to the value of the first temp node [/list=1]
• 01-29-2002
ss3x
**concerning item number 2.set head node to another temp node (there are two temp nodes) **

how can head point to two nodes in a signly linked list?
• 01-29-2002
Unregistered
Goal: create new list by reversing nodes in old list without destroying old list:

Plan:
1)declare a new list newList:
2)declare a new list called tempList:
3)copy old list to tempList:
4)find end of tempList;
5)copy end of tempList to head of newList
6)delete end of tempList;
7)find new end of tempList;
8)copy new end of tempList to end of newList
9)repeat 7 and 8 as long as there are nodes to copy
10)print out newList;
11)print out old list.
• 01-29-2002
ss3x
correct, that solution works, while using O(N) extra space, that is the size of the new list. in order for me to meet the O(1) extra space i would need to do this using the above method of reversing the links, as a pointer or two will take up a constant amount of extra space in addition to the O(N) that my original list takes.
• 01-29-2002
Uraldor
for single-way linked lists like this:

tail->node2

Code:

```Node* prev = NULL; Node* ptr = head; // swap the pointers around while(ptr->next != NULL) {         Node* next = ptr->next;         ptr->next = prev;         prev = ptr;         ptr = next; } // last node ptr->next = prev; // switch the head and tail ptr = head; head = tail; tail = ptr;```
for double-way linked lists like this:

0<->node1<->node2<->NULL
tail->node2

Code:

```Node* ptr = head; // swap the pointers around while(ptr->next != NULL) {         Node* next = ptr->next;         ptr->next = ptr->prev;         ptr->prev = next;                 // go through prev because we switched next and prev         ptr = ptr->prev; } // last node ptr->next = ptr->prev; ptr->prev = NULL // switch the head and tail ptr = head; head = tail; tail = ptr;```
NOTE: this code hasn't been tested/compiled. Should give you an idea though

hope this helps
U.
• 01-29-2002
ss3x
Uraldor: thanks for the info, i worked it into this, however i loose the last element of my original last.. IE. 5 4 3 2 1 will only get me 4 3 2 1 now.. i'm confused.. here is my snippet:

void bigoh_one(){

batter_node *prev=NULL;
batter_node *ptr=first;
//current_batter = first;
//test_pointer = first;
//temp_ptr = first;

while((ptr->next) !=NULL)
{
batter_node* next=ptr->next;
ptr->next=prev;
prev=ptr;
ptr=next;
//cout<<prev->batter_name<<endl;
}

ptr->next=prev;

ptr=first;
first=NULL;
cout<<ptr->batter_name<<endl;
while((prev->next)){
cout<<prev->batter_name<<endl;
prev=prev->next;
}

cout<<"OUT OF LOOP"<<endl;
//first=test_pointer;
cout<<ptr->batter_name<<endl;
exit(0);
}//closes big oh one

gracias
• 01-29-2002
Uraldor
try this:

Code:

```void bigoh_one(void) {         batter_node *prev = NULL;         batter_node *ptr = first;         while(ptr && ptr->next != NULL)         {                 batter_node* next = ptr->next;                 ptr->next = prev;                 prev = ptr;                 ptr = next;         }                 if(ptr)         {                 ptr->next = prev;                 first = ptr;         }                 while(prev)         {                 cout<< prev->batter_name << endl;                 prev = prev->next;         } }//closes big oh one```
• 01-30-2002
ss3x
thanks for the quick response buddy, but i saw that i was setting the ptr in the loop, so i just cout the value once before the loop then it worked.

thanks for the help its much appreciated