面试题16 反转链表
思路 当我们调整节点i的next指针时，需要知道i的前一个节点，当i的next指向前一节点时，我们就无法找到i的下一个节点，所以我们还需要保存i的下一个节点。
代码
struct node * reverseList(struct node *head){
struct node *p,*pre,*next,*reverseHead = NULL;
pre=NULL;
p=head;
//如果链表只有一个节点 直接返回
if (p->next==NULL) {
return p;
}
while (p!=NULL) {
next=p->next;
//如果p是尾节点 那么p就是反转过后的头节点
if (next==NULL) {
reverseHead=p;
}
p->next=pre;
pre=p;
p=next;
}
return reverseHead;
}
递归代码
//递归反转链表
void DiguireverseList(struct node *pre,struct node *p,struct node *next){
next=p->next;
//如果下一个节点为空 那么尾节点指向前一个节点 并且设置反转过后的头节点为p
if (next==NULL) {
p->next=pre;
DiguireverseHead=p;
//否则 p指向前一个节点 并移动pre，p递归调用函数
}else{
p->next=pre;
pre=p;
p=next;
DiguireverseList(pre, p, next);
}
}
面试题17 合并两个排序的链表
输入两个递增的链表，合并两个链表使其仍然递增。
思路 比较两个链表的头节点，较小的加入新链表。下一步和上一步相同，递归完成这个过程。
代码
#pragma mark-合并两个递增链表
struct node * merge(struct node *p1,struct node *p2){
if (p1==NULL) {
return p2;
}
if (p2==NULL) {
return p1;
}
struct node *mergeNode=NULL;
if (p1->data<p2->data) {
mergeNode=p1;
mergeNode->next=merge(p1->next, p2);
}else{
mergeNode=p2;
mergeNode->next=merge(p1, p2->next);
}
return mergeNode;
}
面试题18 树的子结构
输入两颗二叉树a和b 判断b是不是a的子结构
思路 首先，遍历a 看a中有没有节点和b的根节点值相等，若有，遍历b看和a是否相同，直到b遍历完
代码
int DoseTree1hasTree2(struct BinaryTreeNode *p1,struct BinaryTreeNode *p2){
if (p2==NULL) {
return 1;
}
if (p1==NULL) {
return 0;
}
if (p1->value!=p2->value) {
return 0;
}
return DoseTree1hasTree2(p1->leftchild, p2->leftchild)&&DoseTree1hasTree2(p1->rightchild, p2->rightchild);
}
int isSubtree(struct BinaryTreeNode *p1,struct BinaryTreeNode *p2){
int result=0;
//首先判断a树中有没有b树的根节点
if (p1 != NULL && p2 != NULL) {
if (p1->value==p2->value) {
result=DoseTree1hasTree2(p1, p2);
}
//向左子树找
if (!result) {
result=isSubtree(p1->leftchild, p2);
}
//向右子树找
if (!result) {
result=isSubtree(p1->rightchild, p2);
}
}
return result;
}
面试题19 二叉树的镜像
思路 遍历二叉树,每到一个节点,若他是叶子节点,结束.若不是，交换他的左右节点。
代码
void mirror(struct BinaryTreeNode *p){
if (p->leftchild==NULL && p->rightchild==NULL) {
return;
}
struct BinaryTreeNode *t=p->leftchild;
p->leftchild=p->rightchild;
p->rightchild=t;
if (p->leftchild) {
mirror(p->leftchild);
}
if (p->rightchild) {
mirror(p->rightchild);
}
}
面试题20 顺时针打印矩阵
按从里向外以顺时针的顺序依次打印出每一个数字。
将问题分解为两个问题 打印几圈 每一圈如何打印
代码
//打印一圈
void printCircle(int **numbers,int col,int row,int start){
int endx=col-1-start;
int endy=row-1-start;
int i=0;
//从左向右打
for (i=start; i<=endx; i++) {
printf("%d",numbers[start][i]);
}
//从上往下打 endy要大于start
if (start<endy) {
for (i=start+1; i<=endy; i++) {
printf("%d",numbers[i][endx]);
}
}
//从右往左打 至少两行两列
if (start<endy&&start<endx) {
for (i=endx-1; i>=start; i--) {
printf("%d",numbers[endy][i]);
}
}
//从下往上打 至少两行三列
if (start<endy-1&&start<endx) {
for (i=endy-1; i>=start+1; i--) {
printf("%d",numbers[i][start]);
}
}
}
void Printclock(int **numbers,int col,int row){
int start=0;
while (col>start*2&&row>start*2) {
printCircle(numbers,col,row,start);
++start;
}
}