C++ Linking Node Question

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

>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]

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]

**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?

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.

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.

for single-way linked lists like this:

head->node1->node2->NULL
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
head->node1
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.

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

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

---

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