Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita5a19e1

Browse files
authored
Added tasks 236-295
1 parent439dadc commita5a19e1

File tree

21 files changed

+726
-0
lines changed

21 files changed

+726
-0
lines changed

‎README.md

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -246,6 +246,7 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
246246
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
247247
|-|-|-|-|-|-
248248
| 0019 |[Remove Nth Node From End of List](src/main/cpp/g0001_0100/s0019_remove_nth_node_from_end_of_list/Solution.cpp)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, Two_Pointers, Linked_List, Big_O_Time_O(L)_Space_O(L) | 0 | 100.00
249+
| 0234 |[Palindrome Linked List](src/main/cpp/g0201_0300/s0234_palindrome_linked_list/Solution.cpp)| Easy | Top_100_Liked_Questions, Two_Pointers, Stack, Linked_List, Recursion, Big_O_Time_O(n)_Space_O(1) | 154 | 83.63
249250

250251
####Day 4 Linked List
251252

@@ -261,6 +262,7 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
261262

262263
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
263264
|-|-|-|-|-|-
265+
| 0226 |[Invert Binary Tree](src/main/cpp/g0201_0300/s0226_invert_binary_tree/Solution.cpp)| Easy | Top_100_Liked_Questions, Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) | 2 | 45.75
264266

265267
####Day 7 Tree
266268

@@ -278,6 +280,7 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
278280

279281
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
280282
|-|-|-|-|-|-
283+
| 0230 |[Kth Smallest Element in a BST](src/main/cpp/g0201_0300/s0230_kth_smallest_element_in_a_bst/Solution.cpp)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Binary_Search_Tree, Big_O_Time_O(n)_Space_O(n) | 7 | 94.52
281284

282285
####Day 10 Graph/BFS/DFS
283286

@@ -364,7 +367,10 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
364367

365368
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
366369
|-|-|-|-|-|-
370+
| 0283 |[Move Zeroes](src/main/cpp/g0201_0300/s0283_move_zeroes/Solution.cpp)| Easy | Top_100_Liked_Questions, Array, Two_Pointers, Big_O_Time_O(n)_Space_O(1) | 6 | 98.89
367371
| 0001 |[Two Sum](src/main/cpp/g0001_0100/s0001_two_sum/Solution.cpp)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Array, Hash_Table, Big_O_Time_O(n)_Space_O(n) | 4 | 94.42
372+
| 0238 |[Product of Array Except Self](src/main/cpp/g0201_0300/s0238_product_of_array_except_self/Solution.cpp)| Medium | Top_100_Liked_Questions, Array, Prefix_Sum, Big_O_Time_O(n^2)_Space_O(n) | 21 | 88.52
373+
| 0239 |[Sliding Window Maximum](src/main/cpp/g0201_0300/s0239_sliding_window_maximum/Solution.cpp)| Hard | Top_100_Liked_Questions, Array, Heap_Priority_Queue, Sliding_Window, Queue, Monotonic_Queue, Big_O_Time_O(n\*k)_Space_O(n+k) | 164 | 80.55
368374

369375
####Udemy Two Pointers
370376

@@ -392,12 +398,15 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
392398
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
393399
|-|-|-|-|-|-
394400
| 0021 |[Merge Two Sorted Lists](src/main/cpp/g0001_0100/s0021_merge_two_sorted_lists/Solution.cpp)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Linked_List, Recursion, Big_O_Time_O(m+n)_Space_O(m+n) | 0 | 100.00
401+
| 0234 |[Palindrome Linked List](src/main/cpp/g0201_0300/s0234_palindrome_linked_list/Solution.cpp)| Easy | Top_100_Liked_Questions, Two_Pointers, Stack, Linked_List, Recursion, Big_O_Time_O(n)_Space_O(1) | 154 | 83.63
395402

396403
####Udemy Tree Stack Queue
397404

398405
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
399406
|-|-|-|-|-|-
400407
| 0543 |[Diameter of Binary Tree](src/main/cpp/g0501_0600/s0543_diameter_of_binary_tree/Solution.cpp)| Easy | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) | 4 | 95.38
408+
| 0226 |[Invert Binary Tree](src/main/cpp/g0201_0300/s0226_invert_binary_tree/Solution.cpp)| Easy | Top_100_Liked_Questions, Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) | 2 | 45.75
409+
| 0236 |[Lowest Common Ancestor of a Binary Tree](src/main/cpp/g0201_0300/s0236_lowest_common_ancestor_of_a_binary_tree/Solution.cpp)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) | 13 | 55.40
401410

402411
####Udemy Trie and Heap
403412

@@ -499,6 +508,7 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
499508

500509
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
501510
|-|-|-|-|-|-
511+
| 0226 |[Invert Binary Tree](src/main/cpp/g0201_0300/s0226_invert_binary_tree/Solution.cpp)| Easy | Top_100_Liked_Questions, Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) | 2 | 45.75
502512

503513
####Day 13 Tree
504514

@@ -532,11 +542,13 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
532542

533543
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
534544
|-|-|-|-|-|-
545+
| 0240 |[Search a 2D Matrix II](src/main/cpp/g0201_0300/s0240_search_a_2d_matrix_ii/Solution.cpp)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Matrix, Divide_and_Conquer, Big_O_Time_O(n+m)_Space_O(1) | 40 | 84.33
535546

536547
####Day 5 Array
537548

538549
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
539550
|-|-|-|-|-|-
551+
| 0238 |[Product of Array Except Self](src/main/cpp/g0201_0300/s0238_product_of_array_except_self/Solution.cpp)| Medium | Top_100_Liked_Questions, Array, Prefix_Sum, Big_O_Time_O(n^2)_Space_O(n) | 21 | 88.52
540552
| 0560 |[Subarray Sum Equals K](src/main/cpp/g0501_0600/s0560_subarray_sum_equals_k/Solution.cpp)| Medium | Top_100_Liked_Questions, Array, Hash_Table, Prefix_Sum, Big_O_Time_O(n)_Space_O(n) | 54 | 92.60
541553

542554
####Day 6 String
@@ -601,11 +613,13 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
601613

602614
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
603615
|-|-|-|-|-|-
616+
| 0230 |[Kth Smallest Element in a BST](src/main/cpp/g0201_0300/s0230_kth_smallest_element_in_a_bst/Solution.cpp)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Binary_Search_Tree, Big_O_Time_O(n)_Space_O(n) | 7 | 94.52
604617

605618
####Day 18 Tree
606619

607620
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
608621
|-|-|-|-|-|-
622+
| 0236 |[Lowest Common Ancestor of a Binary Tree](src/main/cpp/g0201_0300/s0236_lowest_common_ancestor_of_a_binary_tree/Solution.cpp)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Big_O_Time_O(n)_Space_O(n) | 13 | 55.40
609623

610624
####Day 19 Graph
611625

@@ -639,6 +653,7 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
639653

640654
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
641655
|-|-|-|-|-|-
656+
| 0283 |[Move Zeroes](src/main/cpp/g0201_0300/s0283_move_zeroes/Solution.cpp)| Easy | Top_100_Liked_Questions, Array, Two_Pointers, Big_O_Time_O(n)_Space_O(1) | 6 | 98.89
642657

643658
####Day 4 Two Pointers
644659

@@ -903,6 +918,7 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
903918

904919
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
905920
|-|-|-|-|-|-
921+
| 0287 |[Find the Duplicate Number](src/main/cpp/g0201_0300/s0287_find_the_duplicate_number/Solution.cpp)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Two_Pointers, Bit_Manipulation, Big_O_Time_O(n)_Space_O(n) | 74 | 75.71
906922

907923
####Day 6
908924

@@ -918,6 +934,7 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
918934

919935
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
920936
|-|-|-|-|-|-
937+
| 0240 |[Search a 2D Matrix II](src/main/cpp/g0201_0300/s0240_search_a_2d_matrix_ii/Solution.cpp)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Matrix, Divide_and_Conquer, Big_O_Time_O(n+m)_Space_O(1) | 40 | 84.33
921938

922939
####Day 9
923940

@@ -1121,6 +1138,7 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
11211138

11221139
|<!----> |<!----> |<!----> |<!----> |<!----> |<!---->
11231140
|-|-|-|-|-|-
1141+
| 0283 |[Move Zeroes](src/main/cpp/g0201_0300/s0283_move_zeroes/Solution.cpp)| Easy | Top_100_Liked_Questions, Array, Two_Pointers, Big_O_Time_O(n)_Space_O(1) | 6 | 98.89
11241142

11251143
####Day 7 Array
11261144

@@ -1276,6 +1294,16 @@ Cpp-based LeetCode algorithm problem solutions, regularly updated.
12761294
| 0338 |[Counting Bits](src/main/cpp/g0301_0400/s0338_counting_bits/Solution.cpp)| Easy | Dynamic_Programming, Bit_Manipulation, Udemy_Bit_Manipulation, Big_O_Time_O(num)_Space_O(num) | 0 | 100.00
12771295
| 0322 |[Coin Change](src/main/cpp/g0301_0400/s0322_coin_change/Solution.cpp)| Medium | Top_100_Liked_Questions, Array, Dynamic_Programming, Breadth_First_Search, Algorithm_II_Day_18_Dynamic_Programming, Dynamic_Programming_I_Day_20, Level_2_Day_12_Dynamic_Programming, Big_O_Time_O(m\*n)_Space_O(amount) | 12 | 97.65
12781296
| 0300 |[Longest Increasing Subsequence](src/main/cpp/g0201_0300/s0300_longest_increasing_subsequence/Solution.cpp)| Medium | Top_100_Liked_Questions, Array, Dynamic_Programming, Binary_Search, Algorithm_II_Day_16_Dynamic_Programming, Binary_Search_II_Day_3, Dynamic_Programming_I_Day_18, Udemy_Dynamic_Programming, Big_O_Time_O(n\*log_n)_Space_O(n) | 4 | 94.11
1297+
| 0295 |[Find Median from Data Stream](src/main/cpp/g0201_0300/s0295_find_median_from_data_stream/MedianFinder.cpp)| Hard | Top_100_Liked_Questions, Sorting, Two_Pointers, Design, Heap_Priority_Queue, Data_Stream, Big_O_Time_O(n\*log_n)_Space_O(n) | 231 | 98.67
1298+
| 0287 |[Find the Duplicate Number](src/main/cpp/g0201_0300/s0287_find_the_duplicate_number/Solution.cpp)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Two_Pointers, Bit_Manipulation, Binary_Search_II_Day_5, Big_O_Time_O(n)_Space_O(n) | 74 | 75.71
1299+
| 0283 |[Move Zeroes](src/main/cpp/g0201_0300/s0283_move_zeroes/Solution.cpp)| Easy | Top_100_Liked_Questions, Array, Two_Pointers, Algorithm_I_Day_3_Two_Pointers, Programming_Skills_I_Day_6_Array, Udemy_Arrays, Big_O_Time_O(n)_Space_O(1) | 6 | 98.89
1300+
| 0240 |[Search a 2D Matrix II](src/main/cpp/g0201_0300/s0240_search_a_2d_matrix_ii/Solution.cpp)| Medium | Top_100_Liked_Questions, Array, Binary_Search, Matrix, Divide_and_Conquer, Data_Structure_II_Day_4_Array, Binary_Search_II_Day_8, Big_O_Time_O(n+m)_Space_O(1) | 40 | 84.33
1301+
| 0239 |[Sliding Window Maximum](src/main/cpp/g0201_0300/s0239_sliding_window_maximum/Solution.cpp)| Hard | Top_100_Liked_Questions, Array, Heap_Priority_Queue, Sliding_Window, Queue, Monotonic_Queue, Udemy_Arrays, Big_O_Time_O(n\*k)_Space_O(n+k) | 164 | 80.55
1302+
| 0238 |[Product of Array Except Self](src/main/cpp/g0201_0300/s0238_product_of_array_except_self/Solution.cpp)| Medium | Top_100_Liked_Questions, Array, Prefix_Sum, Data_Structure_II_Day_5_Array, Udemy_Arrays, Big_O_Time_O(n^2)_Space_O(n) | 21 | 88.52
1303+
| 0236 |[Lowest Common Ancestor of a Binary Tree](src/main/cpp/g0201_0300/s0236_lowest_common_ancestor_of_a_binary_tree/Solution.cpp)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Data_Structure_II_Day_18_Tree, Udemy_Tree_Stack_Queue, Big_O_Time_O(n)_Space_O(n) | 13 | 55.40
1304+
| 0234 |[Palindrome Linked List](src/main/cpp/g0201_0300/s0234_palindrome_linked_list/Solution.cpp)| Easy | Top_100_Liked_Questions, Two_Pointers, Stack, Linked_List, Recursion, Level_2_Day_3_Linked_List, Udemy_Linked_List, Big_O_Time_O(n)_Space_O(1) | 154 | 83.63
1305+
| 0230 |[Kth Smallest Element in a BST](src/main/cpp/g0201_0300/s0230_kth_smallest_element_in_a_bst/Solution.cpp)| Medium | Top_100_Liked_Questions, Depth_First_Search, Tree, Binary_Tree, Binary_Search_Tree, Data_Structure_II_Day_17_Tree, Level_2_Day_9_Binary_Search_Tree, Big_O_Time_O(n)_Space_O(n) | 7 | 94.52
1306+
| 0226 |[Invert Binary Tree](src/main/cpp/g0201_0300/s0226_invert_binary_tree/Solution.cpp)| Easy | Top_100_Liked_Questions, Depth_First_Search, Breadth_First_Search, Tree, Binary_Tree, Data_Structure_I_Day_12_Tree, Level_2_Day_6_Tree, Udemy_Tree_Stack_Queue, Big_O_Time_O(n)_Space_O(n) | 2 | 45.75
12791307
| 0023 |[Merge k Sorted Lists](src/main/cpp/g0001_0100/s0023_merge_k_sorted_lists/Solution.cpp)| Hard | Top_100_Liked_Questions, Top_Interview_Questions, Heap_Priority_Queue, Linked_List, Divide_and_Conquer, Merge_Sort, Big_O_Time_O(k\*n\*log(k))_Space_O(log(k)) | 7 | 98.72
12801308
| 0022 |[Generate Parentheses](src/main/cpp/g0001_0100/s0022_generate_parentheses/Solution.cpp)| Medium | Top_100_Liked_Questions, Top_Interview_Questions, String, Dynamic_Programming, Backtracking, Algorithm_II_Day_11_Recursion_Backtracking, Udemy_Backtracking/Recursion, Big_O_Time_O(2^n)_Space_O(n) | 0 | 100.00
12811309
| 0021 |[Merge Two Sorted Lists](src/main/cpp/g0001_0100/s0021_merge_two_sorted_lists/Solution.cpp)| Easy | Top_100_Liked_Questions, Top_Interview_Questions, Linked_List, Recursion, Data_Structure_I_Day_7_Linked_List, Algorithm_I_Day_10_Recursion_Backtracking, Level_1_Day_3_Linked_List, Udemy_Linked_List, Big_O_Time_O(m+n)_Space_O(m+n) | 0 | 100.00
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
// #Easy #Top_100_Liked_Questions #Depth_First_Search #Breadth_First_Search #Tree #Binary_Tree
2+
// #Data_Structure_I_Day_12_Tree #Level_2_Day_6_Tree #Udemy_Tree_Stack_Queue
3+
// #Big_O_Time_O(n)_Space_O(n) #2024_05_24_Time_2_ms_(45.75%)_Space_11.2_MB_(98.21%)
4+
5+
/**
6+
* Definition for a binary tree node.
7+
* struct TreeNode {
8+
* int val;
9+
* TreeNode *left;
10+
* TreeNode *right;
11+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
12+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14+
* };
15+
*/
16+
classSolution {
17+
public:
18+
TreeNode*invertTree(TreeNode* root) {
19+
if (root ==nullptr) {
20+
returnnullptr;
21+
}
22+
TreeNode* temp = root->left;
23+
root->left =invertTree(root->right);
24+
root->right =invertTree(temp);
25+
return root;
26+
}
27+
};
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
226\. Invert Binary Tree
2+
3+
Easy
4+
5+
Given the`root` of a binary tree, invert the tree, and return_its root_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/03/14/invert1-tree.jpg)
10+
11+
**Input:** root =[4,2,7,1,3,6,9]
12+
13+
**Output:**[4,7,2,9,6,3,1]
14+
15+
**Example 2:**
16+
17+
![](https://assets.leetcode.com/uploads/2021/03/14/invert2-tree.jpg)
18+
19+
**Input:** root =[2,1,3]
20+
21+
**Output:**[2,3,1]
22+
23+
**Example 3:**
24+
25+
**Input:** root =[]
26+
27+
**Output:**[]
28+
29+
**Constraints:**
30+
31+
* The number of nodes in the tree is in the range`[0, 100]`.
32+
*`-100 <= Node.val <= 100`
Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
// #Medium #Top_100_Liked_Questions #Depth_First_Search #Tree #Binary_Tree #Binary_Search_Tree
2+
// #Data_Structure_II_Day_17_Tree #Level_2_Day_9_Binary_Search_Tree #Big_O_Time_O(n)_Space_O(n)
3+
// #2024_05_24_Time_7_ms_(94.52%)_Space_22.5_MB_(58.62%)
4+
5+
/**
6+
* Definition for a binary tree node.
7+
* struct TreeNode {
8+
* int val;
9+
* TreeNode *left;
10+
* TreeNode *right;
11+
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
12+
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
13+
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
14+
* };
15+
*/
16+
classSolution {
17+
private:
18+
int k;
19+
int count =0;
20+
int val;
21+
22+
public:
23+
intkthSmallest(TreeNode* root,int k) {
24+
this->k = k;
25+
calculate(root);
26+
return val;
27+
}
28+
29+
private:
30+
voidcalculate(TreeNode* node) {
31+
if (node->left ==nullptr && node->right ==nullptr) {
32+
count++;
33+
if (count == k) {
34+
val = node->val;
35+
}
36+
return;
37+
}
38+
if (node->left !=nullptr) {
39+
calculate(node->left);
40+
}
41+
count++;
42+
if (count == k) {
43+
val = node->val;
44+
return;
45+
}
46+
if (node->right !=nullptr) {
47+
calculate(node->right);
48+
}
49+
}
50+
};
Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
230\. Kth Smallest Element in a BST
2+
3+
Medium
4+
5+
Given the`root` of a binary search tree, and an integer`k`, return_the_ <code>k<sup>th</sup></code>_smallest value (**1-indexed**) of all the values of the nodes in the tree_.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/01/28/kthtree1.jpg)
10+
11+
**Input:** root =[3,1,4,null,2], k = 1
12+
13+
**Output:** 1
14+
15+
**Example 2:**
16+
17+
![](https://assets.leetcode.com/uploads/2021/01/28/kthtree2.jpg)
18+
19+
**Input:** root =[5,3,6,2,4,null,null,1], k = 3
20+
21+
**Output:** 3
22+
23+
**Constraints:**
24+
25+
* The number of nodes in the tree is`n`.
26+
* <code>1 <= k <= n <= 10<sup>4</sup></code>
27+
* <code>0 <= Node.val <= 10<sup>4</sup></code>
28+
29+
**Follow up:** If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?
Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
// #Easy #Top_100_Liked_Questions #Two_Pointers #Stack #Linked_List #Recursion
2+
// #Level_2_Day_3_Linked_List #Udemy_Linked_List #Big_O_Time_O(n)_Space_O(1)
3+
// #2024_05_24_Time_154_ms_(83.63%)_Space_116.7_MB_(68.62%)
4+
5+
/**
6+
* Definition for singly-linked list.
7+
* struct ListNode {
8+
* int val;
9+
* ListNode *next;
10+
* ListNode() : val(0), next(nullptr) {}
11+
* ListNode(int x) : val(x), next(nullptr) {}
12+
* ListNode(int x, ListNode *next) : val(x), next(next) {}
13+
* };
14+
*/
15+
classSolution {
16+
public:
17+
boolisPalindrome(ListNode* head) {
18+
int len =0;
19+
ListNode* right = head;
20+
// Calculate the length
21+
while (right !=nullptr) {
22+
right = right->next;
23+
len++;
24+
}
25+
// Reverse the right half of the list
26+
len = len /2;
27+
right = head;
28+
for (int i =0; i < len; i++) {
29+
right = right->next;
30+
}
31+
ListNode* prev =nullptr;
32+
while (right !=nullptr) {
33+
ListNode* next = right->next;
34+
right->next = prev;
35+
prev = right;
36+
right = next;
37+
}
38+
// Compare left half and right half
39+
for (int i =0; i < len; i++) {
40+
if (prev !=nullptr && head->val == prev->val) {
41+
head = head->next;
42+
prev = prev->next;
43+
}else {
44+
returnfalse;
45+
}
46+
}
47+
returntrue;
48+
}
49+
};
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
234\. Palindrome Linked List
2+
3+
Easy
4+
5+
Given the`head` of a singly linked list, return`true` if it is a palindrome.
6+
7+
**Example 1:**
8+
9+
![](https://assets.leetcode.com/uploads/2021/03/03/pal1linked-list.jpg)
10+
11+
**Input:** head =[1,2,2,1]
12+
13+
**Output:** true
14+
15+
**Example 2:**
16+
17+
![](https://assets.leetcode.com/uploads/2021/03/03/pal2linked-list.jpg)
18+
19+
**Input:** head =[1,2]
20+
21+
**Output:** false
22+
23+
**Constraints:**
24+
25+
* The number of nodes in the list is in the range <code>[1, 10<sup>5</sup>]</code>.
26+
*`0 <= Node.val <= 9`
27+
28+
**Follow up:** Could you do it in`O(n)` time and`O(1)` space?
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
// #Medium #Top_100_Liked_Questions #Depth_First_Search #Tree #Binary_Tree
2+
// #Data_Structure_II_Day_18_Tree #Udemy_Tree_Stack_Queue #Big_O_Time_O(n)_Space_O(n)
3+
// #2024_05_24_Time_13_ms_(55.40%)_Space_16_MB_(48.50%)
4+
5+
/**
6+
* Definition for a binary tree node.
7+
* struct TreeNode {
8+
* int val;
9+
* TreeNode *left;
10+
* TreeNode *right;
11+
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
12+
* };
13+
*/
14+
classSolution {
15+
public:
16+
TreeNode*lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
17+
if (root ==nullptr) {
18+
returnnullptr;
19+
}
20+
if (root->val == p->val || root->val == q->val) {
21+
return root;
22+
}
23+
TreeNode* left =lowestCommonAncestor(root->left, p, q);
24+
TreeNode* right =lowestCommonAncestor(root->right, p, q);
25+
if (left !=nullptr && right !=nullptr) {
26+
return root;
27+
}
28+
if (left !=nullptr) {
29+
return left;
30+
}
31+
return right;
32+
}
33+
};

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp