题目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;
    }