《剑指Offer》题目解析(5)

题目7 链表倒数第k个结点

题目描述

输入一个链表,输出该链表中倒数第k个结点。

题目解析

我们很容易可以想到,由于这是一个单向链表,所以我们可以第一遍先遍历这个链表,看有多少个结点(假设为n),然后计算出pos=n-k+1,然后我们只需要再遍历一遍这个链表,输出第n-k+1个结点的值即可。
但是要注意鲁棒性。我们要考虑,如果这个链表为空呢?如果这个链表的结点数不到k个呢?那就需要对代码进行补充和完善。

代码

ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
        if (pListHead == NULL)
            return NULL;
        ListNode* list1 = pListHead;
        int count=1;
        int pos = 0;
        while (list1)
        {
            ++count;
            list1 = list1->next;
        }
        if (count<=k)
            return list1;
        pos = count - k + 1;
        int n = 1;
        ListNode* list2 = pListHead;
        while (list2 && n < pos - 1)
        {
            list2 = list2->next;
            ++n;
        }
        return list2;

    }

题目8 翻转链表

题目描述

输入一个链表,反转链表后,输出新链表的表头。

题目解析

首先我们应该考虑两个问题(鲁棒性):
1. 链表为空呢?返回空。
2. 链表就只有一个结点呢?返回这个结点。

其它一般情况就是多个结点了。为了正确翻转一个链表,需要调整链表中指针的方向。我们假设有下面三个结点:a->b->c,假设我们要翻转b的next指向a,那么指向a之后,b和c之间的联系就断了,因此我们需要把结点c的地址保存下来。也就是说,我们在调整结点b的next指针的时候,除了需要知道结点b本身,还需要知道结点b的前一个结点a,因为我们要把结点b的next指针指向a。同时,我们还需要实现保存b的一个结点c,以防止链表断开。

我们新建一个next指针,让它来保存b指针的next所指向的地址,然后把a的next指向NULL,然后令node=a,然后把lnode=b;这个时候,进入下一个循环,next指向了c,然后把b的next指向了a,然后令node=b,然后将lnode往下指向c;下一个循环,next=空了,然后把c的next指向了b,然后node=c,然后lnode=空。这个时候判断了lnode为空,结束循环,形成了a<-b<-c

代码

ListNode* ReverseList(ListNode* pHead) {
    if (pHead == NULL)
        return NULL;
    ListNode *node = NULL;
    ListNode *lnode = pHead;
    while(lnode!= NULL){
        ListNode *next = lnode->next;
        lnode->next = node;
        node = lnode;
        lnode = next;

    }
    return node;
}

题目9 合并两个排序的链表

题目描述

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

题目解析

一定要考虑鲁棒性
1. 若第一个链表为空,则直接返回第2个;
2. 若第二个链表为空,则直接返回第1个;
3. 其实若两个链表都为空的话,在第一个if语句判断的时候返回了第二个链表,而第2个链表为空,所以正好也是返回了NULL。
4. 这个时候我们新建一个result的链表存储结果,并为空,对于头结点来说,判断第一个链表和第二个链表的值,若第一个小于第二个,则把第一个链表的头结点给result,然后继续往下进行递归调用Merge函数(Merge(pHead1->next,pHead2));否则,把第二个链表的头结点给result,继续往下进行递归调用Merge函数(Merge(pHead1,pHead2->next)。

代码

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1==NULL)
        return pHead2;
    if(pHead2==NULL)
        return pHead1;
    ListNode* result=NULL;
    if(pHead1->val<pHead2->val)
    {
        result=pHead1;
        result->next=Merge(pHead1->next,pHead2);
    }
    else
    {
        result=pHead2;
        result->next=Merge(pHead1,pHead2->next);
    }
    return result;
}

题目10 树的子结构

题目描述

输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)

题目解析

第一步在树A中查找与根节点的值一样的结点,这实际上就是树的遍历。如HasSubtree()函数中所述。如果根值相同,则去继续比较,否则有A的左子树和B比较,如果还不行就用A的右子树和B比较。
我们一定要注意边界条件的检查,即检查空指针。当树A或B为空的时候,定义相应的输出。本代码里面就是if不符合之后直接返回result。
第二步是判断树A中以R为根节点的子树是不是和B具有相同的结构,这里也是用递归来实现的,如果A为空了B还不是空的,那么B肯定不是A的子树;如果B空了A还没空,那么肯定也不是;如果两个结点值不一样,那就返回false;如果值相同,则继续对左子树和右子树进行比较。
一个可以提现专业的细节:double和float表示小数的时候都有误差,所以判断两个小数的时候不能直接判断相等,而是要判断他们的误差是不是在一个很小的范围内,如果很小,就认为相等。所以可以定义下面的函数:

bool Equal(double a,double b)
{
    if((num1-num2>-0.0000001)&&(num1-num2<0.0000001)
        return true;
    else
        return false;
}

代码

bool HasSub(TreeNode* root1, TreeNode* root2)
    {
        if(root1 ==NULL && root2 !=NULL)
            return false;
        if(root2==NULL)
            return true;
        if(root1->val != root2->val)
            return false;
        return HasSub(root1->left,root2->left)&&HasSub(root1->right,root2->right);

    }
    bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
    {
        bool result = false;
        if(pRoot1!=NULL && pRoot2!=NULL)
        {
            if(pRoot1->val == pRoot2->val)
                result=HasSub(pRoot1,pRoot2);
            if(!result)
                result=HasSubtree(pRoot1->left,pRoot2);
            if(!result)
                result=HasSubtree(pRoot1->right,pRoot2);
        }

        return result;
    }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注