Thread: Traverse a linked list from end to start

If it is a singly-linked list, then you just create a recursive function that goes from the start to the end of the list. As you start to return from all the recursive calls after reaching the end of the list, you do whatever it is you want to have happen:

Code:

void ReverseTraverse( list* pHead )
{
    if( pHead != NULL )
    {
        ReverseTraverse(pHead->pNext);
        DoWhatever(pHead);
    }
}

If, for instance, DoWhatever prints the contents of the nodes, this will print them in reverse order. If you place the call to DoWhatever before the recursive call, then the nodes are printed in forward order, i.e.:

Code:

void ForwardTraverse( list* pHead )
{
    if( pHead != NULL )
    {
        DoWhatever(pHead);
        ForwardTraverse(pHead->pNext);
    }
}

>If it is a singly-linked list, then you just create a recursive
>function that goes from the start to the end of the list.
For a single linked list that solution is elegant, but not always practical depending on the size of the list. In my experience it has always been better to start out with a double linked list from the start so that you save yourself a lot of trouble solving problems such as this. It is of course, a matter of preference.

-Prelude

Code:

NODE *reverse (NODE *pList)
{
 int counter = 0;
 NODE *pNewList;

 if (pList)                  /* list not empty */
 {
  if (pList->link)          /* not last element in list */
  {
   counter++;
   
   pNewList = reverse (pList->link);

   counter--;
   
   pList->link->link = pList;
  }
  
  else                       /* last element */
   pNewList = pList;
 }

 else                        /* empty list */
  return NULL;

 if (!counter)
  pList->link = NULL;

 return pNewList;
}