1 // ListNode 2 typedef struct LNode { 3 int key; 4 struct LNode *next; 5 }LNode;
分析:这是一道很有意思的面试题,此题以及此题的变体经常出现在各大公司的面试、笔试中。
看到这道题后,第一反应是从头到尾输出比较简单。然后经过分析,这道题有以下几种解决方法:
-
将链表中节点的指针反转过来,然后在从头到尾输出节点中的值
-
当要倒置输出值时,我们会想到用栈来实现。所以这种方法是,遍历链表节点中的值,依次入栈,最后弹栈输出
仔细分析这两种方法,解决问题都需要两步。方法一显然不是面试官想要的算法,而方法二需要维护一个额外的栈,在不借用STL容器时,实现起来比较麻烦,那么有没有一步到位的算法呢?
答案是肯定的,仔细分析第二种方法,需要用到栈来实现这个函数,而递归本质上就是一个栈结构。于是想到要用递归的思想来解决问题。下面贴出用递归实现的代码,这类问题要理解,并且能够运用这种递归思想来解决类似的问题:
1 // given a head pointer, print key from the end to the beginning 2 void printListReversely(LNode *head) { 3 if (head) { 4 if (head->next) 5 printListReversely(head->next); 6 } 7 printf("%d ", head->key); 8 }
扩展:
-
给定一个未知长度的字符串,从尾到头输出一个字符窜(在不使用string.h文件中strlen函数的前提下)
-
定义一个函数求字符串的长度,要求函数内部不能声明任何变量
1 // print string reversely 2 void printStringReversely(const char *str) { 3 if (*str != '