Maddening Linked List problem

Question

This has been plaguing me for weeks. It's something really simple, I know it. Every time I print a singly linked list, it prints an address at the end of the list.

#include <iostream>
using namespace std;

struct node
{
  int info;
  node *link;
};

node *before(node *head);
node *after(node *head);
void middle(node *head, node *ptr);
void reversep(node *head, node *ptr);

node *head, *ptr, *newnode;

int main()
{
head = NULL;
ptr = NULL;
newnode = new node;
head = newnode;

for(int c1=1;c1<11;c1++)
{
  newnode->info = c1;
  ptr = newnode;
  newnode = new node;
  ptr->link = newnode;
  ptr = ptr->link;
}

ptr->link=NULL;

head = before(head);
head = after(head);
middle(head, ptr);
//reversep(head, ptr);

ptr = head;
cout<<ptr->info<<endl;
while(ptr->link!=NULL)
{ 
ptr=ptr->link;
  cout<<ptr->info<<endl;
}

system("Pause");
return 0;  
}

node *before(node *head)
{
  node *befnode;
  befnode = new node;

  cout<<"What should go before the list?"<<endl;
  cin>>befnode->info;

  befnode->link = head;
  head = befnode;

  return head;
}

node *after(node *head)
{
  node *afnode, *ptr2;
  afnode = new node;

  ptr2 = head;

  cout<<"What should go after the list?"<<endl;
  cin>>afnode->info;

  ptr2 = afnode;
  afnode->link=NULL;

  ptr2 = head;
  return ptr2;
}

void middle(node *head, node *ptr)
{
  int c1 = 0, c2 = 0;
  node *temp, *midnode;

  ptr = head;
  while(ptr->link->link!=NULL)
  {
    ptr=ptr->link;
    c1++;
  }

  c1/=2;  
  c1-=1;

  ptr = head;

  while(c2<c1)
  {
    ptr=ptr->link;
    c2++;
  }

  midnode = new node;

  cout<<"What should go in the middle of the list?"<<endl;
  cin>>midnode->info;
  cout<<endl;

  temp=ptr->link;
  ptr->link=midnode;
  midnode->link=temp;
}

void reversep(node *head, node *ptr)
{
  node *last, *ptr2;   

  ptr=head;
  ptr2=head;

  while(ptr->link!=NULL)
    ptr = ptr->link;

  last = ptr;

  cout<<last->info;

  while(ptr!=head)
  {
    while(ptr2->link!=ptr)
      ptr2=ptr2->link;

    ptr = ptr2;
    cout<<ptr->info;
  }
}

I'll admit that this is class work, but even the professor can't figure it out, and says that its probably something insignificant that we're overlooking, but I can't put my mind to rest until I find out what it is.

Answer 1

There are two problems here:

1. In your initial loop which creates the list, you don't set the info of the last node. This is what causes the random-looking value to be displayed at the end. This is the relevant code:

   for(int c1=1;c1<11;c1++)
   {
     newnode->info = c1;
     ptr = newnode;
     newnode = new node;
     ptr->link = newnode;
     ptr = ptr->link;
   }    
   ptr->link=NULL;
   

   As you can see, the last node to be created will never have its info set.

2. In the after function, you don't actually connect the new node. You need to find the last node in the list, and set its link to the new node.