Thread: C++ Linking Node Question

  1. #1
    Registered User
    Join Date
    Jan 2002
    Posts
    63

    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
    SS3X

  2. #2
    Unregistered
    Guest
    >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]

  3. #3
    Registered User
    Join Date
    Jan 2002
    Posts
    552
    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]

  4. #4
    Registered User
    Join Date
    Jan 2002
    Posts
    63
    **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?
    SS3X

  5. #5
    Unregistered
    Guest
    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.

  6. #6
    Registered User
    Join Date
    Jan 2002
    Posts
    63
    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.
    SS3X

  7. #7
    Registered User
    Join Date
    Dec 2001
    Posts
    421
    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.
    Quidquid latine dictum sit, altum sonatur.
    Whatever is said in Latin sounds profound.

  8. #8
    Registered User
    Join Date
    Jan 2002
    Posts
    63
    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

  9. #9
    Registered User
    Join Date
    Dec 2001
    Posts
    421

    Talking

    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
    Quidquid latine dictum sit, altum sonatur.
    Whatever is said in Latin sounds profound.

  10. #10
    Registered User
    Join Date
    Jan 2002
    Posts
    63
    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
    SS3X

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. help me debug this linked list !
    By Dark Angel in forum C Programming
    Replies: 6
    Last Post: 04-18-2008, 02:10 PM
  2. help! Placement of nodes in a Linked List
    By lostmyshadow in forum C Programming
    Replies: 6
    Last Post: 12-17-2007, 01:21 PM
  3. Replies: 3
    Last Post: 03-04-2005, 02:46 PM
  4. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  5. Big help in Astar search code...
    By alvifarooq in forum C++ Programming
    Replies: 6
    Last Post: 09-24-2004, 11:38 AM