考察知识点： 树的遍历、递归、深度优先搜索 题目分析：  题目要求找到牛群中的最高牛，即树中的最大结点。只需要遍历一遍树即可。  树的遍历一般使用递归的方法： 若是一颗空树，直接返回最高牛是0; 若是只有一个结点的树，那么最高牛就是该结点。 否则最高牛是树根左子树和右子树中的最高牛。 所用编程语言： C++ /** * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * TreeNode(int x) : val(x), left(nullptr), right(nul...

考察知识点： 链表、STL 题目分析：  题目中使用的链表不方便进行向前查询，所以可以将链表中的值放入vector数组中，以快速进行随机查询。  回文串有两种情况： 奇数回文串。例如 1,2,3,4,3,2,1 偶数回文串。例如 1,2,3,4,4,3,2,1  解题时，可以使用中心扩展法，即遍历整个链表，将链表中的每一个节点看作中点，使用left和right指针分别向左和向右遍历牛群编号，判断其是否满足回文串的要求，并找到最长的回文串。使用该方法时，要考虑到奇数回文串和偶数回文串的情况，两种情况下的回文串取最长的一个。  可以先获取回文串头节点start和尾结点end在vector数组中...

考察知识点： 链表、双指针 题目分析：  判断是否是回文串，可以通过使用双指针，一个指针l从左边开始向右移动，另一个指针r从右边开始向左移动。在l < r的前提下，当两个指针指向的值不相同时，就说明不是回文串。正常结束就说明是回文串。  但是本题中使用链表来存储数据，不能向前搜索，可以提前将链表中的数据放入vector容器中，就可以很方便的执行上述算法。 所用编程语言： C++ /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) ...

考察知识点： 链表、链表取中点、归并排序、链表合并 题目分析：  题目要求对一个链表进行排序。可以使用归并排序的方法，每次找到链表的中点，以此作为分界点，将该点左边（包括该点）与右边这两个子问题分别看成一个完成的排序问题（调用sortList）进行排序。因为sortList函数返回值应该是排序好的链表的头节点，只需要将两个排好序的链表合并即可。  例如{5,9,2,7,3}  注意用双指针找到的中点，如果链表是偶数，那么中点索引恰好是链表中结点数的一半。如果链表是奇数，那么中点索引是中间的节点，而不是length / 2这样的向0取整。  分成这样的子问题后，从底部归并即可得到原问题的解。 ...

考察知识点： 链表 题目分析： 每一次遍历一遍vector,找到指针指向的val最小的那个指针，保存这个指针以及指向这个指针的指针。 通过这个指针将节点插入到新链表末尾，通过指向该指针的指针来使该指针指向下一个结点。 因为每一次遍历都能找到一个要插入到链表中的结点，所以一共需要遍历n次，每次需要查看链表数量(m)的节点。算法复杂度为O(mn)。 所用编程语言： C++ /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * ...

考察知识点： 链表、双指针 题目分析： 首先获取到整个链表的长度length，观察到每移动length次，链表就会变成原来的样子。 用k对length取模得到n,移动这n次即可得到答案。 用双指针找到倒数第n个点，把他作为头节点，把前面的节点插入到链表末尾就能得到最终结果。 所用编程语言： C++ /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: ...

考察知识点： 链表 题目分析：  新建两个链表，一个链表用来存储比x小的节点，另一个存储大于等于x的节点。  遍历一遍所给链表，将每个节点分到新建的两个链表上，最后将大于等于x节点的链表插入到小于x节点的末尾即可。 所用编程语言： C++ /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿...

考察知识点： 链表 题目分析：  这道题和常见的使用快慢指针判断是否有环是不一样的。这道题中的链表中每一个指针都是独一无二的，所以快慢指针根本无法发挥作用。但是这道题测试用例太弱了，估计是像{3,2,0,-4,2,0,-4,2,0,-4,2,0,-4,2,0,-4,2,0,-4}这样手动{-4,2,0}循环的。  实际上每过一个牛的编号就将他加入到集合中，保证他只出现一次就可以了。 所用编程语言： C++ /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), nex...

考察知识点： 链表、大数加法、模拟 题目分析：  链表中低位排在前，可以模拟我们在生活中加法的计算方法，从个位开始加起，得到的新的数中的每一位都是两个数中对应数位的和再加上进位t。 例如：54321 + 9876 = 64197 计算过程如下：  注意在最后要判断t的值，如果t的值大于0,那么需要创建一个新的结点（增加一个数位） 所用编程语言： C++ /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ c...

考察知识点： 链表 题目分析：  可以新建一个head节点，方便处理l1或l2为nullptr的情况。整体思路就是比较两个链表指针所指向的值，将值大的放到新链表的末尾，之后更新指针。  例如链表{4,5,3,5,4}{4,8,1,6,4} 新链表：  如果l1所指向的值大于等于l2所指向的值，那么就将l1插入到新链表，反之将l2插入到新链表。一开始l1和l2所指向的值均为4,故将l1插入到新链表；然后l1的值为5,l2的值仍为4,将l1插入到新链表。  直到l1或l2指向了nullptr时，将非空的链表直接插入到新链表。 所用语言： C++ /** * struct ListNode ...

考察知识点： 链表、翻转链表 题目分析：  首先找到left和right所指向的位置，确定翻转链表的边界。如{1,2,3,4,5},2,4  在找i时可以记录它的前驱节点l，方便在翻转链表后重新插回原链表。j的后继节点r也同样需要记录。这样就可以将关注点放在i～j节点之间。  然后翻转链表即可。使用一个指针n遍历i～j，需要记录n的前驱prev和后继next节点。  每次将n->next更新为prev即可翻转，prev更新为n，n更新为next，next再更新为n->next。  全部翻转完后将翻转后的链表插入回原链表即可。翻转后l后面应插入j，r前应连接i。  注意l节点可...

考察知识点： 链表、链表反转 题目分析：  首先找到一个组中的最后一个节点，即从头节点开始往下走k - 1个节点，这组从头节点到我们找到的最后一个节点间的所有节点是一组。例如{1,2,3,4,5,6,7,8},3  接着，将该段链表翻转。翻转时需要记录一个节点的前驱和后继节点。记录前驱节点是为了翻转时将节点n的指向前驱节点，记录后继节点是为了能让节点n再更新到反转前链表中n的下一个节点。  翻转时，只需要将n的next指针更改即可  然后要更新n、prev、next的值  重复上述过程，直到n指向了pnext,即n指向了不属于该组的节点。  在将一组翻转后，可以将pnext作为头节点，...

考察知识点： 链表、双指针 解答方法：  为了找到倒数第n个点，可以使用双指针的方法，首先将i指向头节点，j指向与i距离为n - 1的点，例如测试用例 {1,2,3,4,5,6,7,8,9} 5：  将j移动到最后一个结点，i和j要同时移动：  这样就能找到倒数第5个点。移动的时候可以使用prev指针记录i的上一个结点，方便调整指针。  在找到结点i后，利用prev耐心调整指针即可，注意prev在初始化后可能不会更新，例如（{1,2,3,4,5} 5）因为此时i结点根本不需要移动，head就是倒数第n个结点。此时对prev分情况讨论即可。 找到想要移动的i结点： 移动i结点： 所用编程...

考察知识点： 链表 解答方法： 题目给出链表已经按照非降序排列，那么如果一些牛的编号相同的话，那么他们一定是连在一起的。可以遍历一遍链表，从头节点开始，找到该节点的下一个结点（即跳过与自身编号相同的结点），然后更新到这个结点，重复上述过程直至到达链表尾。 所用编程语言： C++ /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代...