题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创
建任何新的结点，只调整指针的指向。
比如将二元查找树
10
//
614
1111
481216
转换成双向链表
4=6=8=10=12=14=16。
例外。下面我们用两种不同的递归思路来分析。
思路一：当我们到达某一结点准备调整以该结点为根结点的子树时，先调整其左子树将
左子树转换成一个排好序的左子链表，再调整其右子树转换右子链表。最近链接左子链表的
最右结点(左子树的最大结点)、当前结点和右子链表的最左结点(右子树的最小结点).
从树的根结点开始递归调整所有结点。
思路二：我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果
我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整
当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个
排序双向链表了。
参考代码：
首先我们定义二元查找树结点的数据结构如下：
structBSTreeNode//anodeinthebinarysearchtree
(
intm_nValue;//valueofnode
BSTreeNode*m_pLeft;//leftchildofnode
BSTreeNode*m_pRight;//rightchildofnode
)；
思路一对应的代码：
/////〃〃〃〃〃///〃〃〃〃///〃〃〃〃//////〃〃〃/////〃〃〃///////〃〃
IICovertasubbinary-search-treeintoasorteddouble-linkedlist
//Input:pNode-theheadofthesubtree
//asRight-whetherpNodeistherightchildofitsparent
//Output:ifasRightistrue,returntheleastnodeinthesub-tree
//elsereturnthegreatestnodeinthesub-tree
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH
BSTreeNode*ConvertNode(BSTreeNode*pNode,boolasRight)
if(!pNode)
returnNULL;
BSTreeNode*pLeft=NULL;
BSTreeNode*pRight=NULL;
//Converttheleftsub-tree
if(pNode->m_pLeft)
pLeft=ConvertNode(pNode->m_pLeft,false);
//Connectthegreatestnodeintheleftsub-treetothecurrentnode
if(pLeft)
{
pLeft->m_pRight=pNode;
pNode->m_pLeft=pLeft;
}
//Converttherightsub-tree
if(pNode->m_pRight)
pRight=ConvertNode(pNode->m_pRight,true);
//Connecttheleastnodeintherightsub-treetothecurrentnode
if(pRight)
pNode->m_pRight=pRight;
pRight->m_pLeft=pNode;
)
BSTreeNode*pTemp=pNode;
//Ifthecurrentnodeistherightchildofitsparent,
//returntheleastnodeinthetreewhoserootisthecurrentnode
if(asRight)
while(pTemp->m_pLeft)
pTemp=pTemp->m_pLeft;
11Ifthecurrentnodeistheleftchildofitsparent,
//returnthegreatestnodeinthetreewhoserootisthecurrentnode
else
while(pTemp->m_pRight)
pTemp=pTemp->m_pRight;
returnpTemp;
IICovertabinarysearchtreeintoasorteddouble-linkedlist
//Input:theheadoftree
//Output:theheadofsorteddouble-linkedlist
//〃〃〃/〃〃/〃/〃〃〃/〃〃〃〃〃/〃/〃///〃〃〃/〃〃〃〃〃///〃/〃/〃
BSTreeNode*Convert(BSTreeNode*pHeadOfTree)
//Aswewanttoreturntheheadofthesorteddouble-linkedlist,
//wesetthesecondparametertobetrue
returnConvertNode(pHeadOfTree,true);
思路二对应的代码：
/〃〃/〃〃〃/〃////〃〃〃/〃〃//〃〃///////〃/〃〃//〃〃〃〃////////〃/
//Covertasubbinary-search-treeintoasorteddouble-linkedlist
//pLastNodelnList-thetailofthedouble-linkedlist
IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIH
voidConvertNode(BSTreeNode*pNode,BSTreeNode*&pLastNodelnList)
if(pNode==NULL)
return;
BSTreeNode*pCurrent=pNode;
if(pCurrent->m_pLeft!=NULL)
ConvertNode(pCurrent->m_pLeft,pLastNodelnList);
//Putthecurrentnodeintothedouble-linkedlist
pCurrent->m_pLeft=pLastNodelnList;
if(pLastNodelnList!=NULL)
pLastNodelnList->m_pRight=pCurrent;
pLastNodelnList=pCurrent;
if(pCurrent->m_pRight!=NULL)
ConvertNode(pCurrent->m_pRight,pLastNodelnList);
////〃〃//〃///〃/〃〃〃/〃/〃〃〃/〃//////〃〃〃〃///〃〃/////////〃〃
//Covertabinarysearchtreeintoasorteddouble-linkedlist
//Input:pHeadOfTree-theheadoftree
BSTreeNode*Convert_Solution1(BSTreeNode*pHeadOfTree)
BSTreeNode*pLastNodelnList=NULL;
ConvertNode(pHeadOfTree,pLastNodelnList);
//Gettheheadofthedouble-linkedlist
BSTreeNode*pHeadOfList=pLastNodelnList;
while(pHeadOfList&&pHeadOfList->m_pLeft)
pHeadOfList=pHeadOfList->m_pLeft;
returnpHeadOfList;
题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、
我看到这道题目时，第一反应就是每次push一个新元素时，将栈里所有逆序元素排序。这
样栈顶元素将是最小元素。但由于不能保证最后push进栈的元素最先出栈，这种思路设计
的数据结构已经不是一个栈了。
在栈里添加一个成员变量存放最小元素（或最小元素的位置）。每次push一个新元素进栈
的时候，如果该元素比当前的最小元素还要小，则更新最小元素。
乍一看这样思路挺好的。但仔细一想，该思路存在一个重要的问题：如果当前最小元素被
pop出去，如何才能得到下一个最小元素？
因此仅仅只添加一个成员变量存放最小元素（或最小元素的位置）是不够的。我们需要一个
辅助栈。每次push一个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元
素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗）push到辅助栈中；
每次pop一个元素出栈的时候，同时.pop辅助栈。
#include
#include
template
public:
CStackWithMin(void){}
virtual-*CStackWithMin(void){}
T&top(void);
constT&top(void)const;
voidpush(constT&value);
voidpop(void);
constT&min(void)const;
private:
T>m_data;//theelementsofstack
size__t>m_minlndex;//theindicesofminimumelements
);
//getthelastelementofmutablestack
template
returnm_data.back();
//getthelastelementofnon-mutablestack
template
//insertanelmentattheendofstack
template
//appendthedataintotheendofm_data
m_data.push_back(value);
//settheindexofminimumelmentinm_dataattheendofm_minlndex
if(m_minlndex.size()==0)
m_minlndex.push_back(O);
if(value m_minlndex.push_back(m_data.size()-1); m_minlndex.push_back(m_minlndex.back()); //ereasetheelementattheendofstack template //popm__data m_data.pop_back(); //popm_minlndex m_minlndex.pop_back(); //gettheminimumelementofstack template assert(m_data.size()>0); assert(m_minlndex.size()>0); returnm_data[m_minlndex.back()]; 举个例子演示上述代码的运行过程： 步骤数据栈辅助栈最小值 l.push3303 2.push43,40,03 3.push23,4,20,0,22 4.push13,4,2,10,0,2,31 5.pop3,4,20,0,22 6.pop3,40,03 7.push03,4,00,0,20 讨论：如果思路正确，编写上述代码不是一件很难的事情。但如果能注意一些细节无疑能在 面试中加分。比如我在上面的代码中做了如下的工作： 用模板类实现。如果别人的元素类型只是Mt类型，模板将能给面试官带来好 印象； 两个版本的top函数。在很多类中，都需要提供const和非const版本的成员 访问函数； min函数中assert.,把代码写的尽量安全是每个软件公司对程序员的要求； 添加一些注释。注释既能提高代码的可读性，又能增加代码量，何乐而不为？ 让自己轻松拿到心仪的Offer。 题目：输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个 例如输入的数组为1,-2,3,10,-4,7,2,-5,和最大的子数组为3,10,-4,7,2,因此输出为 该子数组的和18o 分析：本题最初为2005年浙江大学计算机系的考研题的最后一道程序设计题，在2006年 里包括google在内的很多知名公司都把本题当作面试题。由于本题在网络中广为流传，本 题也顺利成为2006年程序员面试题中经典中的经典。 很容易理解，当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果 当前得到的和是个负数，那么这个和在接下来的累加中应该抛弃并重新清零，不然的话这个 负数将会减少接下来的和。基于这样的思路，我们可以写出如下代码。 IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII IIFindthegreatestsumofallsub-arrays //Returnvalue:iftheinputisvalid,returntrue,otherwisereturnfalse lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll boolFindGreatestSumOfSubArray int*pData,//anarray unsignedintnLength,11thelengthofarray int&nGreatestSum//thegreatestsumofallsub-arrays //iftheinputisinvalid,returnfalse if((pData==NULL)||(nLength==0)) returnfalse; intnCurSum=nGreatestSum=0; for(unsignedinti=0;i nCurSum+=pData; //ifthecurrentsumisnegative,discardit if(nCurSum<0) nCurSum=0; //ifagreatersumisfound,updatethegreatestsum if(nCurSum>nGreatestSum) nGreatestSum=nCurSum; //ifalldataarenegative,findthegreatestelementinthearray if(nGreatestSum==0) nGreatestSum=pData[0]; for(unsignedinti=1;i if(pData>nGreatestSum) nGreatestSum=pData; returntrue; 讨论：上述代码中有两点值得和大家讨论一下： 函数的返回值不是子数组和的最大值，而是一个判断输入是否有效的标志。如 果函数返回值的是子数组和的最大值，那么当输入一个空指针是应该返回什么呢？返回0 那这个函数的用户怎么区分输入无效和子数组和的最大值刚好是。这两中情况呢？基于这 个考虑，本人认为把子数组和的最大值以引用的方式放到参数列表中，同时让函数返回一个 函数是否正常执行的标志。 输入有一类特殊情况需要特殊处理。当输入数组中所有整数都是负数时，子数 组和的最大值就是数组中的最大元素。 题目：输入一个整数和一棵二元树。从树的根结点开始往下访问一直到叶结点所经过的所有 结点形成一条路径。打印出和与输入整数相等的所有路径。 例如输入整数22和如下二元树 512 47 则打印出两条路径：10,12和10,5,7。 二元树结点的数据结构定义为： structBinaryTreeNode//anodeinthebinarytree BinaryTreeNode*m_pLeft;//leftchildofnode BinaryTreeNode*m_pRight;//rightchildofnode 分析：这是百度的一道笔试题，考查对树这种基本数据结构以及递归函数的理解。 当访问到某一结点时，把该结点添加到路径上，并累加当前结点的值。如果当前结点为叶结 点并且当前路径的和刚好等于输入的整数，则当前的路径符合要求，我们把它打印出来。如 果当前结点不是叶结点，则继续访问它的子结点。当前结点访问结束后，递归函数将自动回 到父结点。因此我们在函数退出之前要在路径上删除当前结点并减去当前结点的值，以确保 返回父结点时路径刚好是根结点到父结点的路径。我们不难看出保存路径的数据结构实际上 是一个栈结构，因为路径要与递归调用状态一致，而递归调用本质就是一个压栈和出栈的过 程。 IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII IIFindpathswhosesumequaltoexpectedsum lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll voidFindPath BinaryTreeNode*pTreeNode,//anodeofbinarytree intexpectedSum,//theexpectedsum std::vector int¤tSum//thesumofpath if(ipTreeNode) currentSum+=pTreeNode->m_nValue; path.push_back(pTreeNode->m_nValue); //ifthenodeisaleaf,andthesumissameaspre-defined, //thepathiswhatwewant,printthepath boolisLeaf=(!pTreeNode->m_pLeft&&!pTreeNode->m_pRight); if(currentSum==expectedSum&&isLeaf) std::vector for(;iter!=path.end();++iter) std::cout*iter7t'; std::coutstd::endl; //ifthenodeisnotaleaf,gotoitschildren if(pTreeNode->m_pLeft) FindPath(pTreeNode->m_pLeft,expectedSum,path,currentSum); if(pTreeNode->m_pRight) FindPath(pTreeNode->m_pRight,expectedSum,path,currentSum); //whenwefinishvisitinganodeandreturntoitsparentnode, //weshoulddeletethisnodefromthepathand //minusthenode'svaluefromthecurrentsum currentSum-=pTreeNode->m_nValue; path.pop_back(); 题目：输入n个整数，输出其中最小的k个。 例如输入1,2,3,4,5,6,7和8这8个数字，则最小的4个数字为1,2,3和4。 分析：这道题最简单的思路莫过于把输入的n个整数排序，这样排在最前面的k个数就是 我们可以开辟一个长度为k的数组。每次从输入的n个整数中读入一个数.如果数组中已 经插入的元素少于k个，则将读入的整数直接放到数组中。否则长度为k的数组已经满了， 不能再往数组里插入元素，只能替换了。如果读入的这个整数比数组中已有k个整数的最大 值要小，则用读入的这个整数替换这个最大值；如果读入的整数比数组中已有k个整数的最 大值还要大，则读入的这个整数不可能是最小的k个整数之一，抛弃这个整数。这种思路相 以这种办法要优于前面的思路。 这是我能够想出来的最快的解决方案。不过从给面试官留下更好印象的角度出发，我们可以 进一步把代码写得更漂亮一些。从上面的分析，当长度为k的数组已经满了之后，如果需要 大值的数据结构为最大堆。因此我们可以用堆(heap)来代替数组。 另外，自己重头开始写一个最大堆需要一定量的代码。我们现在不需要重新去发明车轮，因 为前人早就发明出来了。同样，STL中的set和multiset为我们做了很好的堆的实现，我们 可以拿过来用。既偷了懒，又给面试官留下熟悉STL的好印象，何乐而不为之？ #include #include /include usingnamespacestd; typedefmultiset //findkleastnumbersinavector voidFindKLeastNumbers constvector lntHeap&leastNumbers,//kleastnumbers,output unsignedintk leastNumbers.clear(); if(k==0||data.size() vector for(;iter!=data.end();++iter) //iflessthanknumberswasinsertedintoleastNumbers if((leastNumbers.size()) leastNumbers.insert(*iter); //leastNumberscontainsknumbersandit*sfullnow //firstnumberinleastNumbersisthegreatestone lntHeap::iteratoriterFirst=leastNumbers.begin(); //ifislessthanthepreviousgreatestnumber if(*iter<*(leastNumbers.begin())) //replacethepreviousgreatestnumber leastNumbers.erase(iterFirst); 题目：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回 true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的 后序遍历结果： 8 610 //// 57911 因此返回true。 如果输入7、4、6、5,没有哪棵树的后序遍历的结果是这个序列，因此返回false。 分析：这是一道trilogy的笔试题，主要考查对二元查找树的理解。 在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点 小的元素都应该位于序列的左半部分;从第一个大于跟结点开始到跟结点前面的一个元素为 止，所有元素都应该大于跟结点，因为这部分元素对应的是树的右子树。根据这样的划分, 把序列划分为左右两部分，我们递归地确认序列的左、右两部分是不是都是二元查找树。 /〃//〃/〃〃/〃//〃〃〃/〃〃〃〃〃〃〃〃//〃/〃〃〃〃〃〃///〃〃///〃〃 //Verifywhetherasquenceofintegersarethepostordertraversal //ofabinarysearchtree(BST) //Input:squence-thesquenceofintegers //length-thelengthofsquence //Return:returntureifthesquenceistraversalresultofaBST, IIotherwise,returnfalse boolverifySquenceOfBST(intsquence[],intlength) if(squence==NULL||length<=0) //rootofaBSTisattheendofpostordertraversalsquence introot=squence[length-1]; //thenodesinleftsub-treearelessthantheroot inti=0; for(;i if(squence>root) break; //thenodesintherightsub-treearegreaterthantheroot intj=i; for(;j if(squence[j] //verifywhethertheleftsub-treeisaBST boolleft=true; if(i>0) left=verifySquenceOfBST(squence,i); //verifywhethertherightsub-treeisaBST boolright=true; if(i right=verifySquenceOfBST(squence+i,length-i-1); return(left&&right); 题目：输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。句子中单词 以空格符隔开。为简单起见，标点符号和普通字母一样处理。 例如输入"Iamastudent.",则输出"student.aamI", 睐。 由于本题需要翻转句子，我们先颠倒句子中的所有字符。这时，不但翻转了句子中单词的顺 序，而且单词内字符也被翻转了。我们再颠倒每个单词内的字符。由于单词内的字符被翻转 两次，因此顺序仍然和输入时的顺序保持一致。 还是以上面的输入为例子。翻转"Iamastudent.”中所有字符得到".tnedutsamaI",再翻转 每个单词中字符的顺序得到“students,aamI"，正是符合要求的输出。 IIReverseastringbetweentwopointers //Input:pBegin-thebeginpointerinastring //pEnd-theendpointerinastring voidReverse(char*pBegin,char*pEnd) if(pBegin==NULL||pEnd==NULL) while(pBegin chartemp=*pBegin; *pBegin=*pEnd; *pEnd=temp; pBegin++,pEnd /〃///〃〃/〃/〃/〃〃//〃///〃/〃〃〃//////〃〃/〃///〃/〃〃///////〃〃 //Reversethewordorderinasentence,butmaintainthecharacter //orderinsideaword //Input:pData-thesentencetobereversed char*ReverseSentence(char*pData) if(pData==NULL) char*pBegin=pData; char*pEnd=pData; while(*pEnd!=70') pEnd++; pEnd-; //Reversethewholesentence Reverse(pBegin,pEnd); //Reverseeverywordinthesentence pBegin=pEnd=pData; while(*pBegin!=70') if(*pBegin=='') pBegin++; continue; //AwordisbetweenwithpBeginandpEnd,reverseit elseif(*pEnd=="||*pEnd==701) Reverse(pBegin,-pEnd); pBegin=++pEnd; returnpData; 题目：求1+2+...+n,要求不能使用乘除法、for、while、if、else,switch>case等关键字 以及条件判断语句(AB:C)。 分析：这道题没有多少实际意义，因为在软件开发中不会有这么变态的限制。但这道题却能 通常求1+2+…+n除了用公式n(n+1)/2之外，无外乎循环和递归两种思路。由于已经明确 限制for和while的使用，循环己经不能再用了。同样，递归函数也需要用if语句或者条件 判断语句来判断是继续递归下去还是终止递归，但现在题目已经不允许使用这两种语句了。 while达到这个效果。比如定义一个类，我们new—含有n个这种类型元素的数组，那么该 类的构造函数将确定会被调用n次。我们可以将需要执行的代码放到构造函数里。如下代 码正是基于这个思路： classTemp Temp(){++N;Sum+=N;} staticvoidReset(){N=0;Sum=0;} staticintGetSum(){returnSum;} staticintN; staticintSum; intTemp::N=0; intTemp::Sum=0; intsolution1_Sum(intn) Temp::Reset(); Temp*a=newTemp[n]; delete[]a; a=0; returnTemp::GetSum(); 数。一个函数充当递归函数的角色，另一个函数处理终止递归的情况，我们需要做的就是在 两个函数里二选一。从二选一我们很自然的想到布尔变量，比如ture(1)的时候调用第一 个函数，false(0)的时候调用第二个函数。那现在的问题是如和把数值变量n转换成布尔 值。如果对n连续做两次反运算，即!!n,那么非零的n转换为true,0转换为false。有了 上述分析，我们再来看下面的代码： classA; A*Array[2]; classA virtualintSum(intn){return0;} classB:publicA virtualintSum(intn){returnArray[!!n]->Sum(n-1)+n;} intsolution2_Sum(intn) Aa; Bb; Array[O]=&a; Array[1]=&b; intvalue=Array[1]->Sum(n); returnvalue; 这种方法是用虚函数来实现函数的选择。当n不为零时，执行函数B::Sum；当n为。时, 执行A::Sum。我们也可以直接用函数指针数组，这样可能还更直接一些： typedefint(*fun)(int); intsolution3_f1(inti) return0; intsolution3_f2(inti) funf[2]={solution3_f1,solution3_f2}; returni+f[!!i](i-1); 另外我们还可以让编译器帮我们来完成类似于递归的运算，比如如下代码： template enumValue{N=solution4_Sum template<>structsolution4_Sum<1> enumValue{N=1}; solutior)4_Sum<100>::N就是1+2+...+100的结果。当编译器看至I]solution4_Sum<100>时， 就是为模板类solution4_Sum以参数100生成该类型的代码。但以100为参数的类型需要 得到以99为参数的类型，因为solution4_Sum<100>::N=solution4_Sum<99>::N+100。这 个过程会递归一直到参数为1的类型，由于该类型已经显式定义，编译器无需生成，递归 编译到此结束。由于这个过程是在编译过程中完成的，因此要求输入n必须是在编译期间 就能确定，不能动态输入。这是该方法最大的缺点。而且编译器对递归编译代码的递归深度 是有限制的，也就是要求n不能太大。 大家还有更多、更巧妙的思路吗？欢迎讨论“A 题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表 的尾指针。链表结点定义如下：structListNode intm_nKey; ListNode*m_pNext; 分析：为了得到倒数第k个结点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。 可是输入的是单向链表，只有从前往后的指针而没有从后往前的指针。因此我们需要打开我 们的思路。 既然不能从尾结点开始遍历这个链表，我们还是把思路回到头结点上来。假设整个链表有n 个结点，那么倒数第k个结点是从头结点开始的第n-k-1个结点(从0开始计数)。如果我 们能够得到链表中结点的个数n,那我们只要从头结点开始往后走n-k-1步就可以了。如何 得到结点数n这个不难，只需要从头开始遍历链表，每经过一个结点，计数器加一就行了。 二次得到从头结点开始的第n-k-1个结点即倒数第k个结点。 如果链表的结点数不多，这是一种很好的方法。但如果输入的链表的结点个数很多，有可能 不能一次性把整个链表都从硬盘读入物理内存，那么遍历两遍意味着一个结点需要两次从硬 如果我们在遍历时维持两个指针，第一个指针从链表的头指针开始遍历，在第k-1步之前, 第二个指针保持不动；在第k-1步开始，第二个指针也开始从链表的头指针开始遍历。由于 两个指针的距离保持在k-1,当第一个(走在前面的)指针到达链表的尾结点时，第二个指 针(走在后面的)指针正好是倒数第k个结点。 这种思路只需要遍历链表一次。对于很长的链表，只需要把每个结点从硬盘导入到内存一次。 思路一的参考代码： /////〃//////////〃/〃//////〃/〃//〃/////〃////〃///〃////〃/////〃/// //Findthekthnodefromthetailofalist //Input:pListHead-theheadoflist //k-thedistancetothetail //Output:thekthnodefromthetailofalist ListNode*FindKthToTail_Solution1(ListNode*pListHead,unsignedintk) if(pListHead==NULL) //countthenodesnumberinthelist ListNode*pCur=pListHead; unsignedintnNum=0; while(pCur->m_pNext!=NULL) pCur=pCur->m_pNext; nNum++; //ifthenumberofnodesinthelistislessthank //donothing if(nNum //thekthnodefromthetailofalist //isthe(n-k)thnodefromthehead pCur=pListHead; for(unsignedinti=0;i returnpCur; 思路二的参考代码： 〃//〃〃/〃〃〃〃/〃〃/〃〃/〃〃//〃〃〃/〃〃〃〃〃〃〃〃/〃〃〃/〃/〃/ IIInput:pListHead-theheadoflist 〃///〃/〃//〃〃/〃/〃〃/〃//////〃//〃〃/〃〃/〃〃////〃/〃〃〃〃〃〃/ ListNode*FindKthToTail_Solution2(ListNode*pListHead,unsignedintk) ListNode*pAhead=pListHead; ListNode*pBehind=NULL; for(unsignedinti=0;i if(pAhead->m_pNext!=NULL) pAhead=pAhead->m_pNext; //ifthenumberofnodesinthelistislessthank, pBehind=pListHead; //thedistancebetweenpAheadandpBehindisk //whenpAheadarrivesatthetail,p //Behindisatthekthnodefromthetail while(pAhead->m_pNext!=NULL) pBehind=pBehind->m_pNext; returnpBehind; 讨论：这道题的代码有大量的指针操作。在软件开发中，错误的指针操作是大部分问题的根 源。因此每个公司都希望程序员在操作指针时有良好的习惯，比如使用指针之前判断是不是 空指针。这些都是编程的细节，但如果这些细节把握得不好，很有可能就会和心仪的公司失 之交臂。 另外，这两种思路对应的代码都含有循环。含有循环的代码经常出的问题是在循环结束条件 的判断。是该用小于还是小于等于？是该用k还是该用k-1由于题目要求的是从0开始计 数，而我们的习惯思维是从1开始计数，因此首先要想好这些边界条件再开始编写代码， 再者要在编写完代码之后再用边界值、边界值减1、边界值加1都运行一次(在纸上写代码 就只能在心里运行了)。 扩展：和这道题类似的题目还有：输入一个单向链表。如果该链表的结点数为奇数，输出中 间的结点；如果链表结点数为偶数，输出中间两个结点前面的一个。如果各位感兴趣，请自 己分析并编写代码0 题目：输入一个己经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和 输出任意一对即可。 例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。 杂度是0(n2)。 我们假设现在随便在数组中找到两个数。如果它们的和等于输入的数字，那太好了，我们找 到了要找的两个数字；如果小于输入的数字呢？我们希望两个数字的和再大一点。由于数组 已经排好序了，我们是不是可以把较小的数字的往后面移动一个数字？因为排在后面的数字 要大一些，那么两个数字的和也要大一些，就有可能等于输入的数字了；同样，当两个数字 的和大于输入的数字的时候，我们把较大的数字往前移动，因为排在数组前面的数字要小一 些，它们的和就有可能等于输入的数字了。 我们把前面的思路整理一下：最初我们找到数组的第一个数字和最后一个数字。当两个数字 的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数 字往后移动：当相等时，打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。 问题是这样的思路是不是正确的呢？这需要严格的数学证明。感兴趣的读者可以自行证明一 下。 〃Findtwonumberswithasuminasortedarray //Output:tureisfoundsuchtwonumbers,otherwisefalse boolFindTwoNumbersWithSum intdata。,//asortedarray unsignedintlength,//thelengthofthesortedarray intsum,//thesum int&num1,//thefirstnumber,output int&num2//thesecondnumber,output boolfound=false; if(length<1) returnfound; intahead=length-1; intbehind=0; while(ahead>behind) longlongcurSum=data[ahead]+data[behind]; //ifthesumoftwonumbersisequaltotheinput //wehavefoundthem if(curSum==sum) num1=data[behind]; num2=data[ahead]; found=true; //ifthesumoftwonumbersisgreaterthantheinput //decreasethegreaternumber elseif(curSum>sum) ahead //ifthesumoftwonumbersislessthantheinput //increasethelessnumber behind++; 扩展：如果输入的数组是没有排序的，但知道里面数字的范围，其他条件不变，如和在0(n) 题目：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树 的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。例如输入： 输出： 106 11975 定义二元查找树的结点为： structBSTreeNode//anodeinthebinarysearchtree(BST) 分析：尽管我们可能一下子不能理解镜像是什么意思，但上面的例子给我们的直观感觉，就