?
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
?
Follow up:
Can you solve it without using extra space?
题目解释：
?
单链表找环的题目，代码中不开辟新的空间，这道题应该是算法面试和一些书籍上常见的题。
?
这道题，在读书的时候就做过了，不过很久没有搞类似的算法，碰到这道题，还捣鼓了一会，所以说呢，思考后，要及时记录下来，思绪很宝贵，可能转瞬就失去了，不扯了。
?
这道题做完后，发现网上有一篇文章分析、总结得非常好，和大家也分享一下”检测单链表是否有环“。
?
有朋友说要上代码测试的例子，个人觉得必要性不大，
源码都可以保证正确性，在LeetCode上验证过的，大家想要验证的话，自已copy下去，弄个main函数，结果一输出就能跑了。
?
直接上我的源码：
?
复制代码
struct ListNode {
? ? ? int val;
? ? ? ListNode *next;
? ? ? ListNode(int x) : val(x), next(NULL) {}
};
?
class Solution {
public:
? ? ListNode *detectCycle(ListNode *head) {
?
? ? ? ? ListNode *pt1 = head;
? ? ? ? ListNode *pt2 = head;
? ? ? ??
? ? ? ? int steps = 0;
? ? ? ? while(pt2 != NULL && pt2->next != NULL)
? ? ? ? {
? ? ? ? ? ? pt1 = pt1->next;
? ? ? ? ? ? pt2 = pt2->next->next;
?
? ? ? ? ? ? steps++;
?
? ? ? ? ? ? if (pt1 == pt2)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? // 第一次两指针相撞时，环长=步长
? ? ? ? ? ? ? ? ? int ring_len = steps;
?
? ? ? ? ? ? ? ? pt1 = head;
? ? ? ? ? ? ? ? pt2 = head;
?
? ? ? ? ? ? ? ? // pt2先走一个环长，然后在下一个while中，
? ? ? ? ? ? ? ? ? // pt1和pt2一起走，再相撞的话就是环的起始点
? ? ? ? ? ? ? ? ? steps = 0;
? ? ? ? ? ? ? ? while (steps != ring_len)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? pt2 = pt2->next;
? ? ? ? ? ? ? ? ? ? steps++;
? ? ? ? ? ? ? ? }
?
? ? ? ? ? ? ? ? while (pt1 != pt2)
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? pt1 = pt1->next;
? ? ? ? ? ? ? ? ? ? pt2 = pt2->next;
? ? ? ? ? ? ? ? }
?
? ? ? ? ? ? ? ? return pt2;
? ? ? ? ? ? }
?
? ? ? ? }
?
? ? ? ? return NULL;
? ? }
};
复制代码
2、题目 - Maximum Depth of Binary Tree
?
Given a binary tree, find its maximum depth.
?
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
题目解释：
?
给定一个二叉树，找到一条最长的路径
?
这道题就非常简单了，最基本的二叉树深度遍历的小问题，只要这样想，每到一个节点时，让该节点的左子树和右子树分别告诉我它们的最长路径，那么就可以算出这个节点的最长路径了，依次递归下去执行，问题搞定。
?
直接上源码：
?
复制代码
struct TreeNode {
? ? int val;
? ? TreeNode *left;
? ? TreeNode *right;
? ? TreeNode(int x) : val(x), left(NULL), right(NULL) {}
?};
?
class Solution {
public:
? ? int maxDepth(TreeNode *root) {
? ? ? ? if (root == NULL)
? ? ? ? {
? ? ? ? ? ? return 0;
? ? ? ? }
?
? ? ? ? int right_length = maxDepth(root->right);
? ? ? ? int left_lengh = maxDepth(root->left);
?
? ? ? ? // 左右子树，看谁长，就取哪个节点的最长路径
? ? ? ? ?if (left_lengh >= right_length)
? ? ? ? {
? ? ? ? ? ? return left_lengh + 1;
? ? ? ? }
?
? ? ? ? return right_length + 1;
? ? }
};