程序员面试题精选100题(13)－单链表的逆序以及逆序输出

题目：输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。链表结点定义如下：

struct ListNode
{
      int        m_nKey;
      ListNode* m_pNext;
};

ListNode* ReverseIteratively(ListNode* pHead)
{
      ListNode* pReversedHead = NULL;
      ListNode* pNode = pHead;
      ListNode* pPrev = NULL;
      while (pNode != NULL)
      {
            // get the next node, and save it at pNext
            ListNode* pNext = pNode->m_pNext;

            // if the next node is null, the currect is the end of original 
            // list, and it's the head of the reversed list
            if (pNext == NULL)
                  pReversedHead = pNode;

            // reverse the linkage between nodes
            pNode->m_pNext = pPrev;

            // move forward on the the list
            pPrev = pNode;
            pNode = pNext;
      }

      return pReversedHead;
}

解法二：

struct Node  
{  
    int data ;  
    Node *next ;  
};  
typedef struct Node Node ;  
 
Node* ReverseList(Node* head)  
{  
    if (!head || !head->next)  
    {  
        return head;  
    }  
    Node* p1 = head;  
    Node* p2 = p1->next;  
    head->next = NULL;  
    while (p2)  
    {  
          
        p1 = p2;  
        p2 = p2->next;  
        p1->next = head;  
        head = p1;  
    }  
    return head;  
}

解法三：

Node* RecReverseList(Node* head) //递归方法  
{     
    if (!head || !head->next)  
    {  
        return head;  
    }  
    Node *newhead = RecReverseList(head->next);  
    head->next->next = head;  
    head->next = NULL;  
    return newhead;  
}  

递归的解释说明：

上面的递归算法看不懂可以参考下面（其实与上面的递归算法是一样，多了注释而已）：

       // p 为指向非空单链表中第一个结点的指针，本算法逆转链表并返回逆转后的头指针。基本思路是：如果链表中只有一个结点，则空操作，否则先逆转a2开始的链表，然后将 a1联接到逆转后的链表的表尾(即a2)之后。
LinkList reverse(LinkList p)
{
    if(p->next == NULL) return p;   // 链表中只有一个结点，逆转后的头指针不变
    else
    {
        q = p->next;          // q为链表(a2,…an)的头指针
        h = reverse(q);       // 逆转链表(a2,…an)，并返回逆转后的头指针
        q->next = p;          // 将a1联接在a2之后
        p->next = NULL;

        return h;               // (a2,…,an)逆转表的头指针即为(a1,a2,…,an)
    }
}

 

下面是单链表的逆序输出：

递归实现：

void  printSList(slist  * pList)
{
    assert(pList);
     if  (pList  ==  NULL)
         return ;
     if  (pList -> next  ==  NULL)
        printf( " %s " ,  * pList);
     else
    {
        printSList(pList -> next);
        printf( " %s " ,  * pList);
    }
}

栈的实现：

void ReservePrint(List L)
{
assert( NULL != L );
int count = 0;
int temp;
while (NULL != L->Next)
{
++count;
temp = L->data;
stack_s.push( temp);
L = L->Next;
}

while(--count>=0)
{

  temp=stack_s.top()
  stack_s.pop();
  printf(" %d ", temp);
}
数组实现：

用数组保存链表数据，然后从高维向低维输出

 

关于栈的使用：

#include<iostream>
#include<stack>
using namespace std;
stack<char> sts;
void main()
{
 char i,temp;
 for(i=65;i<70;i++)
 {
  sts.push(i);//进栈
  cout<<i<<"  ";
 }
 cout<<endl;
 for(i=65;i<70;i++)
 {
  temp=sts.top();//取栈顶元素
  sts.pop();//出栈
  cout<<temp<<"  ";
 }
 cout<<endl;
}