剑指offer学习笔记：3.4 代码的鲁棒性
容错性是鲁棒性一个重要体现。
防御性编程，预见什么地方可能出问题，并进行定制处理。譬如，在函数入口位置，进行空指针，空字符串判断。
面试题15：链表中倒数第k个节点
题目：输入一个链表，输出该链表中第k个节点。为了符合大多数人习惯，本题从1开始计数，即链表尾节点为倒数第一个节点。
牛客链接 https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) { if (pListHead == NULL || k == 0) // 重要，不判断程序可能会崩溃 { return NULL; } ListNode* head = pListHead; ListNode* index = pListHead; for(int i = 0; i < k; i++) { if (index != NULL) { index = index->next; } else { return NULL; // 链表长度不够k，找不到 } } while(index != NULL) { head = head->next; index = index->next; } return head; } };
解题思路：双指针，第一个指针先走k步。
考察点：1）链表输入为空指针 2）链表总长度小于k 3）k为0
相关题目：求链表中间节点。若链表长度是奇数，返回中间节点，若链表长度是偶数，返回两个中间节点中任意一个。
leetcode链接 https://leetcode-cn.com/problems/middle-of-the-linked-list//** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* middleNode(ListNode* head) { ListNode* fast = head; ListNode* slow = head; while(fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; } };
解题思路：快慢指针
相关题目：判断一个单向链表是否形成环结构。
leetcode链接 https://leetcode-cn.com/problems/linked-list-cycle/ 这个题旁边的示例介绍很奇葩，不用关注，就当普通的判断环写就行/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: bool hasCycle(ListNode *head) { /* // hash表 map<ListNode*, int> list; while(head != NULL) { // cout << head->val << " "; if (list.find(head) != list.end()) { return true; } list[head] = 0; head = head->next; } return false; */ // 快慢指针 if(head == NULL) { return false; } // 因为要通过fast=slow判断是否有环，首位要错开。 // 同时，因为这里取了next，入口处一定要进行指针判空。 ListNode* fast = head->next; ListNode* slow = head; while(fast != NULL && fast->next != NULL) { if (fast == slow) { return true; } fast = fast->next->next; slow = slow->next; } return false; } };
解题思路：有哈希表和快慢指针两种解法。哈希表很好理解，就是把遍历过的节点存入hash表中，遇到新节点进行判断，如果节点已经在表中，则为有环，复杂度为链表长度。快慢指针运用的是在一个环中，速度快与速度慢的进行追击，总会相遇的原理，最坏情况复杂度为n+k，k为环长。环长很长情况下时间可能消耗比较大。
面试题16：反转链表
题目：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点
牛客网链接 https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca?tpId=13&&tqId=11168&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead == NULL || pHead->next == NULL) { return pHead; } /* // 循环写法 // 注意终止条件 ListNode* cur = pHead; ListNode* pre = NULL; while(cur != NULL) { ListNode* next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; */ // 递归写法 ListNode* result = ReverseList(pHead->next); pHead->next->next = pHead; // 注意这里是phead操作，不是result，result就是用于返回的新的头结点，不参与反转操作 pHead->next = NULL; return result; } };
思路：应该有循环和递归两种方式
链表结构
递归：
递归过程示意图
考察点：1）输入链表头指针为null 2）输入链表只有一个节点 3）输入链表有多个节点
面试题17：合并两个有序链表
输入两个递增排序的链表，合并两个链表并使新链表有序。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { // 先判断异常条件 if(pHead2 == NULL) { return pHead1; } if (pHead1 == NULL) { return pHead2; } // 递归写法 ListNode* merge; if (pHead1->val < pHead2->val) { merge = pHead1; merge->next = Merge(pHead1->next, pHead2); } else{ merge = pHead2; merge->next = Merge(pHead1, pHead2->next); } return merge; /* // 遍历写法 ListNode* merge = NULL; ListNode* index1 = pHead1; ListNode* index2 = pHead2; if (index1->val < index2->val) { merge = index1; index1 = index1->next; } else { merge = index2; index2 = index2->next; } ListNode* head = merge; // 注意需要保存下头结点，用于返回 while(index1 != NULL && index2 != NULL) { if (index1->val < index2->val) { merge->next = index1; index1 = index1->next; } else{ merge->next = index2; index2 = index2->next; } merge = merge->next; } while(index1 != NULL) { merge->next = index1; index1 = index1->next; merge = merge->next; } while(index2 != NULL) { merge->next = index2; index2 = index2->next; merge = merge->next; } merge->next = NULL; return head; */ } };
思路：同样有递归和循环两种思路
考察点：1）两个链表都有多个节点，节点值互不相同或存在相同值 2）特殊输入（两个链表中一个或两个头结点为null或两个链表中只有一个节点）
面试题18：树的子结构
题目：输入两棵二叉树A和B，判断B是不是A的子树
牛客网链接 https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&&tqId=11170&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking/* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: bool tree1HasTree2(TreeNode* root1, TreeNode* root2) { // 判断是不是子树 if (root2 == NULL) { return true; } if (root1 == NULL) { return false; } if (root1->val != root2->val) { return false; } return tree1HasTree2(root1->left, root2->left) && tree1HasTree2(root1->right, root2->right); } bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2) { if (pRoot1 == NULL || pRoot2 == NULL) { return false; } bool result = false; // 第一步：遍历二叉树，找到子树根节点 if (pRoot1->val == pRoot2->val) { // root1的根节点和root2的根节点相同 // 第二步：找到树2的根节点后，判断该处结构是不是子树 result = tree1HasTree2(pRoot1, pRoot2); } if (!result) { // 根节点不是，在左子树进行遍历 result = HasSubtree(pRoot1->left, pRoot2); } if (!result) { // 根节点不是，左子树不是，在右子树进行遍历 result = HasSubtree(pRoot1->right, pRoot2); } return result; } };
思路：遍历，当找到节点与B的根节点相同，判断其下子节点是否相同。找根节点是一个递归，判断其下子节点是否相同也为递归。
考察点：写树的代码一定要注意，涉及指针的地方要判空，不然会有风险。
