剑指offer第五天

面试题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;
}
}