当前位置 博文首页 > 自留地：9月10日美团网2014校招研发笔试哈尔滨站
1、链表翻转。给出一个链表和一个数k，比如链表1→2→3→4→5→6，k=2，则翻转后2→1→4→3→6→5，若k=3,翻转后3→2→1→6→5→4，若k=4，翻转后4→3→2→1→5→6，用程序实现
点评：类似编程艺术第1章左旋转字符串，见：http://blog.csdn.net/v_JULY_v/article/details/6322882。
个人想法：按照k把链表分组，每组进行翻转（这里可以定义一个函数，参数：起点，终点/或者是长度k）
具体实现：
???? 【1】首先判断链表从头开始数K个（注意链表长度小于K情况的处理）
???? 【2】每组链表翻转
链表翻转代码如下：
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};//链表的结构体
ListNode *ReverseList(ListNode *pHead)
{
assert(pHead!=NULL);//防止传入的是一个空指针，参数检查很重要！！！一定不要忘记写
ListNode *pReversedList = NULL; //指向反转后的链表的头结点
ListNode *pNode = pHead; //指向断开后链表的后面一段链表的第一个结点
ListNode *pPrev = NULL; //指向断开后链表的前面一段链表的最后一个结点
while(pNode!=NULL)
{
ListNode *pNext = pNode->m_pNext;
if(pNext == NULL)
pReversedList = pNode;
pNode->m_pNext = pPrev; //指向它以前的前驱元素
pPrev = pNode; //前驱后移
pNode = pNext; //当前元素后移
}
return pReversedList;
}
?
?????【3】如果最后的那一组不满足K个的，不用翻转。
2、一个m*n的矩阵，从左到右从上到下都是递增的，给一个数elem，求是否在矩阵中，给出思路和代码
点评：杨氏矩阵查找，见编程艺术第23章：http://blog.csdn.net/v_july_v/article/details/7085669。
个人观点：从矩阵最右上角的那个元素开始，与elem比较，如果小于elem，删元素所在行；如果大于elem，删除元素所在列。结束条件是行列有一个<0，或者与elem相等。
