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 31 | 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 10 | 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 10 | 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; } |
复杂度
