首页 / 算法 / LeetCode算法编程之连载三
LeetCode算法编程之连载三
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode算法编程之连载三，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1867字，纯文字阅读大概需要3分钟。
内容图文
1、题目 - Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull. 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)
{
return0;
}
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;
}
};
原文：http://www.cnblogs.com/derrick/p/4077715.html
内容总结
以上是互联网集市为您收集整理的LeetCode算法编程之连载三全部内容，希望文章能够帮你解决LeetCode算法编程之连载三所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。