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;
}
};
