单向链表逆序输出（写出单向链表的逆置算法）

1.把二查找树转变成排序的双向链表（树）

题目：
输入一棵二查找树，将该二查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ /
6 14
/ / / /
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。

首先我们定义的二查找树节点的数据结构如下：
struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};

2.设计包含min函数的栈（栈）

定义栈的数据结构，要求添加一个min函数，能够得到栈的最小素。
要求函数min、push以及pop的时间复杂度都是O(1)。

3.求子数组的最大和（数组）

题目：
输入一个整形数组，数组里有正数也有负数。
数组中连续的一个或多个整数组成一个子数组，每个子数组都有一个和。
求所有子数组的和的最大值。要求时间复杂度为O(n)。

例如输入的数组为1, -2, 3, 10, -4, 7, 2, -5，和最大的子数组为3, 10, -4, 7, 2，
因此输出为该子数组的和18。

4.在二树中找出和为某一值的所有路径（树）

题目：输入一个整数和一棵二树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。
例如输入整数22和如下二树
10
/ /
5 12
/   /
4     7
则打印出两条路径：10, 12和10, 5, 7。

二树节点的数据结构定义为：
struct BinaryTreeNode // a node in the binary tree
{
int m_nValue; // value of node
BinaryTreeNode *m_pLeft; // left child of node
BinaryTreeNode *m_pRight; // right child of node
};

5.查找最小的k个素（数组）

题目：输入n个整数，输出其中最小的k个。
例如输入1，2，3，4，5，6，7和8这8个数字，则最小的4个数字为1，2，3和4。

第6题（数组）

腾讯面试题：
给你10分钟时间，根据上排给出十个数，在其下排填出对应的十个数
要求下排每个数都是先前上排那十个数在下排出现的次数。
上排的十个数如下：
【0，1，2，3，4，5，6，7，8，9】

例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：

第10题（字符串）

翻转句子中单词的顺序。
题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。

第12题（语法）

题目：求1+2+…+n，
要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句（A?B:C）。

第13题（链表）：

题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
链表结点定义如下：
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};

第14题（数组）：

题目：输入一个已经按升序排序过的数组和一个数字，
在数组中查找两个数，使得它们的和正好是输入的那个数字。
要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。

第15题（树）：

题目：输入一颗二查找树，将该树转换为它的镜像，
即在转换后的二查找树中，左子树的结点都大于右子树的结点。
用递归和循环两种方法完成树的镜像转换。
例如输入：
8
/ /
6 10
// //
5 7 9 11

第16题（树）：

题目（微软）：
输入一颗二树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
例如输入

输出8 6 10 5 7 9 11。

第17题（字符串）：

题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。
分析：这道题是2006年google的一道笔试题。

第20题（字符串）：

题目：输入一个表示整数的字符串，把该字符串转换成整数并输出。
例如输入字符串"345"，则输出整数345。

第21题（数组）

2010年中兴面试题
编程求解：
输入两个整数 n 和 m，从数列1，2，3.......n 中随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.

第22题（推理）：

有4张红色的牌和4张蓝色的牌，主持人先拿任意两张，再分别在A、B、C三人额头上贴任意两张牌，
A、B、C三人都可以看见其余两人额头上的牌，看完后让他们猜自己额头上是什么颜色的牌，
A说不知道，B说不知道，C说不知道，然后A说知道了。
请教如何推理，A是怎么知道的。
如果用程序，又怎么实现呢？

第24题（链表）：

链表操作，单链表就地逆置，

第25题（字符串）：

写一个函数,它的原形是int continumax(char *outputstr,char *intputstr)
功能：
在字符串中找出连续最长的数字串，并把这个串的长度返回，
并把这个最长数字串付给其中一个函数参数outputstr所指内存。
例如："abcd12345ed125ss"的首地址传给intputstr后，函数将返回9，
outputstr所指的值为

26.左旋转字符串（字符串）

27.跳台阶问题（递归）

题目：一个台阶总共有n级，如果一次可以跳1级，也可以跳2级。
求总共有多少总跳法，并分析算法的时间复杂度。

28.整数的二进制表示中1的个数（运算）

题目：输入一个整数，求该整数的二进制表达中有多少个1。
例如输入10，由于其二进制表示为1010，有两个1，因此输出2。

31.华为面试题（搜索）：

一类似于蜂窝的结构的图，进行搜索最短路径（要求5分钟）

32.（数组、规划）

有两个序列a,b，大小都为n,序列素的值任意整数，无序；
要求：通过交换a,b中的素，使[序列a素的和]与[序列b素的和]之间的差最小。
例如:
var a=[100,99,98,1,2, 3];
var b=[1, 2, 3, 4,5,40];

37.（字符串）

有n个长为m+1的字符串，
如果某个字符串的最后m个字符与某个字符串的前m个字符匹配，则两个字符串可以联接，
问这n个字符串最多可以连成一个多长的字符串，如果出现循环，则返回错误。

38.（算法）

百度面试：
1.用天平（只能比较，不能称重）从一堆小球中找出其中唯一一个较轻的，使用x次天平，
最多可以从y个小球中找出较轻的那个，求y与x的关系式。

3.大量的URL字符串，如何从中去除重复的，优化时间空间复杂度

40.百度研发笔试题（栈、算法）

引用自：zp
1)设计一个栈结构，满足一下条件：min，push，pop操作的时间复杂度为O(1)。

当用户输入中国人民的时候，要求返回与这个搭配词组相关的信息。

42.请修改append函数，利用这个函数实现（链表）：

43.递归和非递归俩种方法实现二叉树的前序遍历。

44.腾讯面试题（算法）：

1.设计一个魔方（六面）的程序。
2.有一千万条短信，有重复，以文本文件的形式保存，一行一条，有重复。
请用5分钟时间，找出重复出现最多的前10条。

3.收藏了1万条url，现在给你一条url，如何找出相似的url。（面试官不解释何为相似）

45.雅虎（运算、矩阵）：

1.对于一个整数矩阵，存在一种运算，对矩阵中任意素加一时，需要其相邻（上下左右）

48.微软（运算）：

一个数组是由一个递减数列左移若干位形成的，比如{4，3，2，1，6，5}
是由{6，5，4，3，2，1}左移两位形成的，在这种数组中查找某一个数。

49.一道看上去很吓人的算法面试题（排序、算法）：

如何对n个数进行排序，要求时间复杂度O(n)，空间复杂度O(1)

题目：输入一棵二树的根结点，求该树的深度。

从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

输出该树的深度3。

二树的结点定义如下：

53.字符串的排列（字符串）。

题目：输入一个字符串，打印出该字符串中字符的所有排列。
例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串
abc、acb、bac、bca、cab和cba。

54.调整数组顺序使奇数位于偶数前面（数组）。

55.（语法）

题目：类CMyString的声明如下：
class CMyString
{
public:
      CMyString(char* pData = NULL);
      CMyString(const CMyString& str);
      ~CMyString(void);
      CMyString& operator = (const CMyString& str);

56.最长公共字串（算法、字符串）。

题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，

则字符串一称之为字符串二的子串。

分析：求最长公共子串（Longest Common Subsequence, LCS）是一道非常经典的动态规划题，

因此一些重视算法的公司像MicroStrategy都把它当作面试题。

题目：某队列的声明如下：

60.在O（1）时间内删除链表结点（链表、算法）。

题目：给定链表的头指针和一个结点指针，在O(1)时间删除该结点。链表结点的定义如下：

struct ListNode

{

int m_nKey;

ListNode* m_pNext;

};

分析：这是一道广为流传的Google面试题，能有效考察我们的编程基本功，还能考察我们的反应速度，

61.找出数组中两个只出现一次的数字（数组）

题目：一个整型数组里除了两个数字之外，其他的数字都出现了两次。
请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

分析：这是一道很新颖的关于位运算的面试题。

{

int m_nKey;

ListNode* m_pNext;

};

例如，输入”They are students.”和”aeiou”，

则删除之后的第一个字符串变成”Thy r stdnts.”。

分析：这是一道在网络上广为流传的面试题，据说google曾经采用过这道题。

66.颠倒栈（栈）。

题目：用递归颠倒一个栈。例如输入栈{1, 2, 3, 4, 5}，1在栈顶。
颠倒之后的栈为{5, 4, 3, 2, 1}，5处在栈顶。

67.俩个闲玩娱乐（运算）。

输出旋转数组的最小素。例如数组{3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。

72.（语法）

题目：设计一个类，我们只能生成该类的一个实例。
分析：只能生成一个实例的类是实现了Singleton模式的类型。

分析：可能很多人都写过判断一个字符串是不是对称的函数，这个题目可以看成是该函数的加强版。

题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

75.二叉树两个结点的最低共同父结点（树）

题目：二叉树的结点定义如下：
struct TreeNode
{

请完成函数ComplexNode* Clone(ComplexNode* pHead)，以复制一个复杂链表。
分析：在常见的数据结构上稍加变化，这是一种很新颖的面试题。
要在不到一个小时的时间里解决这种类型的题目，我们需要较快的反应能力，
对数据结构透彻的理解以及扎实的编程功底。

2.给定两个单链表(head1, head2)，检测两个链表是否有交点，如果有返回第一个交点。

78.链表和数组的区别在哪里（链表、数组）？

80.阿里巴巴一道笔试题（运算、算法）

先来几组百度的面试题：

===================

给出这个解答后，面试官有要求只能用一个辅助数组，且要求少遍历一次。

本微软等面试100题系列V0.1版，完。

======================

更多请参见此100题V0.2版：微软、谷歌、百度等公司经典面试100题[第1-60题]。

---------------------------------------------------------------------------------

致各位网友

一、关于本微软等100题系列V0.1版的郑重声明
http://blog.csdn.net/v_JULY_v/archive/2010/12/02/.aspx

三、目前前60题的答案参考早已公布上传，第61-100题的答案在整理中。

所有的资源下载（题目+答案）地址：

http://v_july_v.download.csdn.net/

五、目前，针对本100题系列，我已建一个100题永久讨论组（后面的朋友加Algorithms_4群，见博客公告栏内。）
专门针对这100题各个版本中任何一道题进行讨论、交流、维护、修正。
//预计本微软等面试100题系列V0.2版，相信，会在明年2011年与大家见面，具体待定。

六、一切的详情，还是在本博客里。欢迎，永久关注，此博客。

本博客致力于数据结构之法、算法优化之道

=================================================

更多请参见此100题V0.2版：微软、谷歌、百度等公司经典面试100题[第1-60题]。

本文转自博客园知识天地的博客，原文链接：数据结构+算法面试100题，如需转载请自行联系原博主。

今天的文章单向链表逆序输出（写出单向链表的逆置算法）分享到此就结束了，感谢您的阅读。

单向链表逆序输出（写出单向链表的逆置算法）

相关推荐