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

题目描述

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

题目解析

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

代码

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

代码

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

题目描述

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

题目解析

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

代码

题目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表示小数的时候都有误差,所以判断两个小数的时候不能直接判断相等,而是要判断他们的误差是不是在一个很小的范围内,如果很小,就认为相等。所以可以定义下面的函数:

代码