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