首页 > 代码库 > LeetCode算法编程之连载三
LeetCode算法编程之连载三
1、题目 - Linked List Cycle II
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; }};
LeetCode算法编程之连载三
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。