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