【面试题5】从尾到头打印链表

链表的创建,插入结点,删除结点等操作都只需要20行左右的代码来实现。
链表是一种动态数据结构,因为在创建链表的时候,无须知道链表的长度。当插入一个结点的时候,只需要为新结点分配内存,然后调整指针的指向来确保新结点被链接到链表当中。内存分配不是在创建链表的时候一次完成的,而是每添加一个结点分配一次内存。
如果单向链表的结点定义如下:

struct ListNode
{
   int m_nValue;
   ListNode* m_pNext;
}

1.往链表的末尾中添加一个结点的代码如下:

void AddToTail(ListNode** pHead,int value)
{
    ListNode* pNew=new ListNode();
    pNew->m_nValue=value;
    pNew->m_pNext=NULL;

    if(*pHead==NULL)
    {
       *pHead=pNew;
    }
    else
    {
       ListNode* pNode=*pHead;
       while(pNode->m_pNext!=NULL)
             pNode=pNode->m_pNext;

       pNode->m_pNext=pNew;
    }
 }

2.由于链表中的内存不是一次性分配的,因此我们无法保证链表的内存和数组一样是连续的。因此,如果想在链表中找到它的第i个结点,我们只能从头结点开始,沿着指向下一个结点的指针遍历链表,它的时间效率为O(n)。而在数组中,我们可以根据下标在O(1)时间内找到第i个元素。
下面是在链表中找到第一个含有某值得结点并删除该结点的代码:

void RemoveNode(ListNode** pHead,int value)
{
   if(pHead==NULL||*pHead==NULL)
   return;

   ListNode* pToBeDeleted=NULL:
   if((*pHead)->m_nValue==value)
   {
      pToBeDeleted=*pHead;
      *pHead=(*pHead)->m_pNext;
   }
   else
   {
   ListNode* pNode=*pHead;
   while(pNode->m_pNext!=NULL && pNode->m_pNext->m_nValue!=value)
        pNode=pNode->m_pNext;

   if(pNode->m_pNext!=NULL&& pNode->m_pNext->m_nValue==value)
      {
      pToBeDeleted=pNode->m_pNext;
      pNode->m_pNext=pNode->m_pNext->m_pNext;
      }
   }

   if(pToBeDeleted!=NULL)
   {
     delete pToBeDeleted;
     pToBeDeleted=NULL:
   }
}

题目:输入一个链表的头结点,从尾到头反过来打印出每个结点的值。
分析:
通常打印是一个只读操作,不希望打印的时候修改内容。假设面试官也要求这个题目不能改变链表的结构。接下来想到的解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序,可输出的顺序是从尾到头的顺序。也就是第一个遍历到的结点最后一个输出,最后一个遍历到的结点第一个输出。这是典型的“后进先出”,可以用栈实现这种顺序。每进过一个结点的时候,把该结点放到一个栈中。当遍历完整个链表后,再从栈顶开始逐个输出结点的值,此时输出的结点的顺序已经反转过来了。
这种思路的代码如下:

void PrintListReversingly_Iteratively(ListNode* pHead)
{
  std::stack<ListNode*> node;
  ListNode* pNode=pHead;
  while(pNode!=NULL)
  {
     nodes.push(pNode);
     pNode=pNode->m_pNext;
  }
  while(!nodes.empty())
  {
     pNode=nodes.top();
     printf("%d\t",pNode->m_nValue);
     nodes.pop();
  }
}

既然想到了用栈来实现这个函数,而递归本质上就是一个栈结构。要实现反过来输出链表,我们每访问到一个结点的时候,就先递归输出它后面的结点,再输出该结点自身,这样链表的输出结果就反过来了。
代码如下:

void PrintListReversingly_Recurisively(ListNode* pHead)
{
  if(pHead!=NULL)
  {
    if(pHead->m_pNext!=NULL)
    {
        PrintListReversingly_Recurisively(pHead->m_pNext);
    }
    printf("%d\t",pHead->m_nValue);
 }
}
;