【100題】第58題末尾からチェーンテーブルを出力

一、テーマ
チェーンテーブルのヘッダノードを入力し、各ノードの値を末尾から逆に出力します.チェーンテーブルノードの定義は、struct ListNode{
      int       m_nKey;       ListNode* m_pNext; };
二、分析
 
解法一:チェーンテーブルのリンクノードのポインタを反転させ、チェーンテーブルの方向を変える.そして最初から最後まで出力できます.リファレンス
解法2:チェーンテーブルを最初から最後まで遍歴し、1つのノードを通過するたびに、そのノードをスタックに置く.完全なチェーンテーブルを巡回した後、スタックの上部からノードの値が出力されると、出力されたノードの順序が反転します.この方法は追加のスタックを維持する必要があり、実現するのは面倒です.
解法3:再帰は本質的にスタック構造である.そこで自然と再帰で実現することを思いついた.逆出力チェーンテーブルを実現するには、ノードにアクセスするたびに、その後のノードを再帰的に出力し、そのノード自体を出力します.これにより、チェーンテーブルの出力結果は逆になります.
 
三、コード
このような考え方に基づいて、以下のコードを書くのは難しくありません.
 

void PrintListReversely(ListNode* pListHead)
{
      if(pListHead != NULL)
      {
            if (pListHead->m_pNext != NULL)
                  PrintListReversely(pListHead->m_pNext);
            else 
                  printf("%d", pListHead->m_nKey);
      }
}

 
拡張:この問題には2つの一般的な変形があります:1.末尾から文字列を出力します.       2.関数を定義して文字列の長さを求め、関数内で変数を宣言できないことを要求します.

#include <iostream>
using namespace std; 

void print(char *str)
{
		if(*(str+1)!='\0')
	    	 print(str+1);
    
         printf("%c ",str[0]); 	
}
 

int  getlength(char *str)
{
	if(*str=='\0')
		return 0;
	else
	    return getlength(str+1)+1; 
	
} 
int main()
{
	char *str="abcde"; 
	cout<<getlength(str)<<endl;
	
	print(str); 
}