408算法题leetcode--第23天

236. 二叉树的最近公共祖先

• 236. 二叉树的最近公共祖先\
• 思路：递归，如注释
• 时间和空间：O(n)

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}* };*/
class Solution {
public:TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {// 最近公共祖先：root的两侧分别为p, q；root = p, 且q在左/右子树中，同理root = q, 且p在左右子树中// dfs: 1. 确定参数类型和返回类型，TreeNode*, bool// 2. 终止条件：空节点，null; root == q/p, root// 3. 递归逻辑：后序遍历，如果左右儿子都为空，返回null，如果其中一个不是空，即目标节点if(root == nullptr || root == q || root == p) return root;TreeNode* left = lowestCommonAncestor(root->left, p, q);TreeNode* right = lowestCommonAncestor(root->right, p, q);if(!left && !right) return nullptr;if(left && !right) return left;if(!left && right) return right;return root;}
};

234. 回文链表

• 234. 回文链表
• 思路1：如注释
• 时间和空间：O(n)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:bool isPalindrome(ListNode* head) {// 思路1：转换为数组，然后再判断回文vector<int>v;while(head){v.push_back(head->val);head = head->next;}// 判断回文int size = v.size();for(int i = 0; i < size / 2; i++){if(v[i] != v[size - 1 - i]){return false;}}return true;}
};

• 思路2：快慢指针找到链表中点，后一段链表翻转，然后比较两个链表是否相同
• 时间：O(n)，空间：O(1)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* findMiddle(ListNode* head){// 快慢指针ListNode* fast = head, *slow = head;while(fast->next && fast->next->next){fast = fast->next->next;slow = slow->next;}return slow;}ListNode* reverseList(ListNode* head){// 翻转链表ListNode* pre = nullptr, *cur = head, *next = nullptr;while(cur){next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre;}bool isPalindrome(ListNode* head) {// 快慢指针找到链表中点，后一段链表翻转，然后比较两个链表是否相同if(head == nullptr) return true;// 找中点，奇数个节点时，中间节点放到左边的链表中ListNode* middle = findMiddle(head);// 翻转右边的链表ListNode* right = reverseList(middle->next);// 比较ListNode* p = head, *q = right;while(p && q){if(p->val != q->val){return false;}p = p->next;q = q->next;}// 最好比较完，还原链表return true;}
};

141. 环形链表

• 141. 环形链表
• 思路：如注释
• 时间：O(n)；空间：O(1)

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:bool hasCycle(ListNode *head) {// 思路1：哈希表：如果某个值出现2次，则有环// 思路2：快慢指针，快指针走2，慢指针走1，如果相等则有环if(head == nullptr || head->next == nullptr) return false;ListNode* p = head, *q = head;while(q && q->next){p = p->next;q = q->next->next;if(q == p){return true;}}return false;}
};