logo头像

不忘初心,奋力前行

leetcode题目解析(191107)

Leetcode 234:回文链表

题目描述

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

示例

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

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

解题思路

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

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

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

状态图

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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:翻转二叉树

题目描述

翻转一棵二叉树

示例

示例图

解题思路

代码实现

1
2
3
4
5
6
7
8
9
void invertTree(TreeNode* root) {
if (!root)
return ;
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;
invertTree(root->left);
invertTree(root->right);
}
1
2
3
4
5
6
7
8
9
TreeNode* invertTree(TreeNode* root) {
if (!root)
return nullptr;
TreeNode *right = invertTree(root->right);
TreeNode *left = invertTree(root->left);
root->left = right;
root->right = left;
return root;
}

复杂度

复杂度配图

支付宝打赏 微信打赏 QQ钱包打赏

感觉不错?欢迎给我 打个赏~我将不胜感激!