2019-11-07 242 views 评论

Leetcode题目解析（191107）

标签：leetcode

Leetcode 234：回文链表

题目描述

请判断一个链表是否为回文链表。

示例

示例 1:输入: 1->2
输出: false

示例 2:输入: 1->2->2->1
输出: true

解题思路

我的解题思路很简单：
第一步：寻找到中间结点；第二步，其中一侧进行反转然后进行比较是否相等。

所以代码其实分块很明显。第一部分就是寻找中间结点，同时将前半部分进行链表翻转，这一部分是用快慢指针和翻转链表方法完成，无需解释。然后，对于奇数个结点的链表来说，在完成第一步的时候fast不为空，所以这个时候slow往后走一步，否则不需要走。然后开始比较即可。

具体如图所示，图中的各种状态对应着代码里面状态1/2/3。

状态图

代码实现

bool isPalindrome(ListNode* head) {
    if (!head || !(head-&gt;next))
        return true;
    ListNode* slow = head;
    ListNode* fast = head;
    ListNode* lnode = head;
    ListNode* node = nullptr;
    //完成上述操作为状态1
    //找到中间节点的同时翻转前半部分
    while (fast != nullptr &amp;&amp; fast-&gt;next != nullptr)
    {
        lnode = slow;
        slow = slow-&gt;next;
        fast = fast-&gt;next-&gt;next;
        lnode-&gt;next = node;
        node = lnode;
    }
    //完成上述操作为状态2
    if (fast != nullptr)//奇数个节点的情况
        slow = slow-&gt;next;
        //完成上述操作为状态3
    while (lnode != nullptr &amp;&amp; slow != nullptr)
    {
        if (lnode-&gt;val != slow-&gt;val)
            return false;
        lnode = lnode-&gt;next;
        slow = slow-&gt;next;
    }
    return true;
}

bool isPalindrome(ListNode* head) {

if (!head || !(head->next))

return true;

ListNode* slow = head;

ListNode* fast = head;

ListNode* lnode = head;

ListNode* node = nullptr;

//完成上述操作为状态1

//找到中间节点的同时翻转前半部分

while (fast != nullptr && fast->next != nullptr)

{

lnode = slow;

slow = slow->next;

fast = fast->next->next;

lnode->next = node;

node = lnode;

}

//完成上述操作为状态2

if (fast != nullptr)//奇数个节点的情况

slow = slow->next;

//完成上述操作为状态3

while (lnode != nullptr && slow != nullptr)

{

if (lnode->val != slow->val)

return false;

lnode = lnode->next;

slow = slow->next;

}

return true;

}

执行用时和内存消耗

复杂度配图

Leetcode226：翻转二叉树

题目描述

翻转一棵二叉树

示例

示例图

解题思路

代码实现

void invertTree(TreeNode* root) {
    if (!root)
        return ;
    TreeNode* temp = root-&gt;left;
    root-&gt;left = root-&gt;right;
    root-&gt;right = temp;
    invertTree(root-&gt;left);
    invertTree(root-&gt;right);
}

void invertTree(TreeNode* root) {

if (!root)

return ;

TreeNode* temp = root->left;

root->left = root->right;

root->right = temp;

invertTree(root->left);

invertTree(root->right);

}

TreeNode* invertTree(TreeNode* root) {
    if (!root)
        return nullptr;
    TreeNode *right = invertTree(root-&gt;right);
    TreeNode *left = invertTree(root-&gt;left);
    root-&gt;left = right;
    root-&gt;right = left;
    return root;
}