Skip to content

Commit 10ee431

Browse files
david-legenddavid-legend
committed
added linkedlist and tree questions
1 parent 2d5d9ee commit 10ee431

129 files changed

Lines changed: 3992 additions & 1 deletion

File tree

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

‎README.md‎

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -217,8 +217,77 @@ Below are solutions & questions found under various topics in the book.
217217
* `E` [Two Sum IV - Input is a BST ](leetcode/src/binary_trees/lc_653_two_sum_IV/two_sum.py)
218218
* `E` [Second Minimum Node In a Binary Tree ](leetcode/src/binary_trees/lc_671_second_minimum_node_in_binary_tree/second_minimum_node_in_binary_tree.py)
219219
* `E` [Minimum Distance Between BST Nodes](leetcode/src/binary_trees/lc_783_min_distance_between_bst_nodes/min_distance_between_bst_nodes.py)
220+
* `M` [Unique Binary Search Trees II](lc_95_unique_binary_search_trees_II/unique_binary_search_trees.py)
221+
* `M` [Unique Binary Search Trees](lc_96_unique_binary_search_trees/unique_binary_search_trees.py)
222+
* `M` [Validate Binary Search Tree](lc_98_validate_binary_search_tree/validate_binary_search_tree.py)
223+
* `M` [Recover Binary Search Tree](lc_99_recover_binary_search_trees/recover_binary_search_trees.py)
224+
* `M` [Binary Tree Level Order Traversal](lc_102_binary_tree_level_order_traversal/binary_tree_level_order_traversal.py)
225+
* `M` [Binary Tree Zigzag Level Order Traversal](lc_103_binary_tree_zigzag_level_order_traversal/binary_tree_zigzag_level_order_traversal.py)
226+
* `M` [Construct Binary Tree from Preorder and Inorder Traversal ](lc_105_construct_binary_tree_from_preorder_inorder_traversal/construct_binary_tree_from_preorder_inorder_traversal.py)
227+
* `M` [Construct Binary Tree from Inorder and Postorder Traversal](lc_106_construct_binary_tree_from_inorder_postorder_traversal/construct_binary_tree_from_inorder_postorder_traversal.py)
228+
* `M` [Binary Tree Level Order Traversal II](lc_107_binary_tree_level_order_traversal_II/binary_tree_level_order_traversal.py)
229+
* `M` [Path Sum II](lc_113_path_sum_II/path_sum.py)
230+
* `M` [Flatten Binary Tree to Linked List](lc_114_flatten_binary_tree_to_linkedlist/flatten_binary_tree_to_linkedlist.py)
231+
* `M` [Populating Next Right Pointers in Each Node](lc_116_populate_next_right_pointers_in_each_node/populate_next_right_pointers.py)
232+
* `M` [Populating Next Right Pointers in Each Node II](lc_117_populate_next_right_pointer_in_each_node_II/populate_next_right_pointers.py)
233+
* `M` [Sum Root to Leaf Numbers](lc_129_sum_root_to_leaf_numbers/sum_root_to_leaf_numbers.py)
234+
* `M` [Binary Search Tree Iterator](lc_173_binary_search_tree_iterator/binary_search_tree_iterator.py)
235+
* `M` [Binary Tree Right Side View](lc_199_binary_tree_right_side_view/binary_tree_right_side_view.py)
236+
* `M` [Count Complete Tree Nodes](lc_222_count_complete_tree_nodes/count_complete_tree_nodes.py)
237+
* `M` [Kth Smallest Element in a BST](lc_230_kth_smallest_in_bst/kth_smallest_in_bst.py)
238+
* `M` [Lowest Common Ancestor of a Binary Tree](lc_236_lowest_common_ancestor_of_binary_tree/lowest_common_ancestor_of_binary_tree.py)
239+
* `M` [House Robber III](lc_337_house_robber_III/house_robber.py)
240+
* `M` [Path Sum III](lc_437_path_sum_III/path_sum.py)
241+
* `M` [Serialize and Deserialize BST](lc_449_serialize_deserialize_bst/serialize_deserialize_bst.py)
242+
* `M` [Delete Node in a BST](lc_450_delete_bst_node/delete_bst_node.py)
243+
* `M` [Most Frequent Subtree Sum](lc_508_most_frequent_subtree_sum/most_frequent_subtree_sum.py)
244+
* `M` [Find Bottom Left Tree Value](lc_513_find_bottom_left_tree_value/find_bottom_left_tree_value.py)
245+
* `M` [Find Largest Value in Each Tree Row](lc_515_find_largest_value_in_each_tree_row/find_largest_value_in_each_tree_row.py)
246+
* `M` [Convert BST to Greater Tree](lc_538_convert_bst_to_greater_tree/convert_bst_to_greater_tree.py)
247+
* `M` [Add One Row to Tree](lc_623_add_one_row_to_tree/add_one_row_to_tree.py)
248+
* `M` [Find Duplicate Subtrees](lc_652_find_duplicate_subtrees/find_duplicate_subtrees.py)
249+
* `M` [Maximum Binary Tree](lc_654_maximum_binary_tree/maximum_binary_tree.py)
250+
* `M` [Print Binary Tree](lc_655_print_binary_tree/print_binary_tree.py)
251+
* `M` [Maximum Width of Binary Tree](lc_662_maximum_width_of_binary_tree/maximum_width_of_binary_tree.py)
252+
* `M` [Trim a Binary Search Tree](lc_669_trim_a_binary_search_tree/trim_a_binary_search_tree.py)
253+
* `M` [Longest Univalue Path](lc_687_longest_univalue_path/longest_univalue_path.py)
254+
* `M` [All Nodes Distance K in Binary Tree](lc_863_all_nodes_distance_k_binary_tree/all_nodes_distance_k_binary_tree.py)
255+
* `M` [Smallest String Starting From Leaf](lc_988_smallest_string_starting_from_leaf/smallest_string_starting_from_leaf.py)
256+
* `M` [Maximum Binary Tree II](lc_998_maximum_binary_tree_II/maximum_binary_tree.py)
257+
* `M` [Construct Binary Search Tree from Preorder Traversal](lc_1008_construct_binary_tree_from_preorder_traversal/construct_binary_tree_from_preorder_traversal.py)
258+
* `H` [Binary Tree Maximum Path Sum](lc_124_binary_tree_maximum_path_sum/binary_tree_maximum_path_sum.py)
259+
* `H` [Serialize and Deserialize Binary Tree](lc_297_serialize_and_deserialize_binary_tree/serialize_and_deserialize_binary_tree.py)
220260

221261
<br>
262+
263+
* [LinkedLists](leetcode/src/linkedlist)
264+
* `E` [Merge Two Sorted Lists](leetcode/src/linkedlist/lc_21_merge_two_sorted_lists/merge_two_sorted_lists.py)
265+
* `E` [Remove Duplicates from Sorted List I](leetcode/src/linkedlist/lc_83_remove_duplicates_from_sorted_list/remove_duplicates_from_sorted_list.py)
266+
* `E` [Linked List Cycle](leetcode/src/linkedlist/lc_141_linkedlist_cycle/linkedlist_cycle.py)
267+
* `E` [Intersection of Two Linked Lists](leetcode/src/linkedlist/lc_160_intersection_of_two_linkedlists/intersection_of_two_linkedlists.py)
268+
* `E` [Remove Linked List Elements](leetcode/src/linkedlist/lc_203_remove_linkedlist_elements/remove_linkedlist_elements.py)
269+
* `E` [Reverse Linked List](leetcode/src/linkedlist/lc_206_reverse_linkedlist/reverse_linkedlist.py)
270+
* `E` [Palindrome Linked List](leetcode/src/linkedlist/lc_234_palindrome_linkedlist/palindrome_linkedlist.py)
271+
* `M` [Add Two Numbers](leetcode/src/linkedlist/lc_2_add_two_numbers/add_two_numbers.py)
272+
* `M` [Remove Nth Node From End of List](leetcode/src/linkedlist/lc_19_remove_nth_node_from_list/remove_nth_node_from_list.py)
273+
* `M` [Swap Nodes in Pairs](leetcode/src/linkedlist/lc_24_swap_nodes_in_pairs/swap_nodes_in_pairs.py)
274+
* `M` [Rotate List](leetcode/src/linkedlist/lc_61_rotate_list/rotate_list.py)
275+
* `M` [Remove Duplicates from Sorted List II](leetcode/src/linkedlist/lc_82_remove_duplicates_from_sorted_list_II/remove_duplicates_from_sorted_list_II.py)
276+
* `M` [Partition List](leetcode/src/linkedlist/lc_86_partition_list/partition_list.py)
277+
* `M` [Reverse Linked List II](leetcode/src/linkedlist/lc_92_reverse_linkedlist_II/reverse_linkedlist_II.py)
278+
* `M` [Convert Sorted List to Binary Search Tree](leetcode/src/linkedlist/lc_109_convert_sorted_list_binary_tree/convert_sorted_list_binary_tree.py)
279+
* `M` [Copy List with Random Pointer](leetcode/src/linkedlist/lc_138_copy_list_with_random_pointer/copy_list_with_random_pointer.py)
280+
* `M` [Linked List Cycle II](leetcode/src/linkedlist/lc_142_linkedlist_cycle_II/linkedlist_cycle.py)
281+
* `M` [Reorder List](leetcode/src/linkedlist/lc_143_reorder_list/reorder_list.py)
282+
* `M` [Insertion Sort List](leetcode/src/linkedlist/lc_147_insertion_sort/insertion_sort.py)
283+
* `M` [Sort List](leetcode/src/linkedlist/lc_148_sort_list/sort_list.py)
284+
* `M` [Delete Node in a Linked List](leetcode/src/linkedlist/lc_237_delete_node_in_linkedlist/delete_node_in_linkedlist.py)
285+
* `M` [Odd Even Linked List](leetcode/src/linkedlist/lc_328_odd_even_linkedlist/odd_even_linkedlist.py)
286+
* `M` [Add Two Numbers II](leetcode/src/linkedlist/lc_445_add_two_numbers_II/add_two_numbers.py)
287+
* `M` [Split Linked List in Parts](leetcode/src/linkedlist/lc_725_split_linkedlist_in_parts/split_linkedlist_in_parts.py)
288+
* `H` [Merge k Sorted Lists](leetcode/src/linkedlist/lc_23_merge_k_sorted_lists/merge_k_sorted_lists.py)
289+
* `H` [Reverse Nodes in k-Groups](leetcode/src/linkedlist/lc_25_reverse_nodes_in_k_groups/reverse_nodes_in_k_groups.py)
290+
222291
<br>
223292

224293
## Algorithms

‎blind_75/src/linkedlist/README.md‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
## Blind 75 LinkedList Questions
2+
3+
`E` - Easy, `M` - Medium , `H` - Hard,
4+
5+
* `M` [Remove Nth Node From End of List](lc_19_remove_nth_node_from_list/remove_nth_node_from_list.py)
6+
* `E` [Merge Two Sorted Lists](lc_21_merge_two_sorted_lists/merge_two_sorted_lists.py)
7+
* `E` [Merge k Sorted Lists](lc_23_merge_k_sorted_lists/merge_k_sorted_lists.py)
8+
* `E` [Linked List Cycle](lc_141_linkedlist_cycle/linkedlist_cycle.py)
9+
* `M` [Reorder List](lc_143_reorder_list/reorder_list.py)
10+
* `E` [Reverse Linked List](lc_206_reverse_linkedlist/reverse_linkedlist.py)
11+
12+

‎blind_75/src/linkedlist/lc_141_linkedlist_cycle/README.md‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
# [LC 141. Linked List Cycle - Easy](https://leetcode.com/problems/linked-list-cycle/)
2+
3+
Given head, the head of a linked list, determine if the linked list has a cycle in it.
4+
5+
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
6+
7+
Return true if there is a cycle in the linked list. Otherwise, return false.
8+
9+
### Example 1
10+
11+
![Linked List Cycle Example 1](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist.png)
12+
13+
```
14+
Input: head = [3,2,0,-4], pos = 1
15+
Output: true
16+
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
17+
```
18+
19+
### Example 2
20+
21+
![Linked List Cycle Example 2](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test2.png)
22+
23+
```
24+
Input: head = [1,2], pos = 0
25+
Output: true
26+
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
27+
```
28+
29+
### Example 3
30+
31+
![Linked List Cycle Example 2](https://assets.leetcode.com/uploads/2018/12/07/circularlinkedlist_test3.png)
32+
33+
```
34+
Input: head = [1], pos = -1
35+
Output: false
36+
Explanation: There is no cycle in the linked list.
37+
```
38+
39+
### Constraints:
40+
41+
- The number of the nodes in the list is in the range [0, 104].
42+
- -105 <= Node.val <= 105
43+
- pos is -1 or a valid index in the linked-list.

‎blind_75/src/linkedlist/lc_141_linkedlist_cycle/linkedlist_cycle.py‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
def has_cycle(head):
2+
if not head: return False
3+
4+
slow = fast = head
5+
while fast.next and fast.next.next:
6+
slow, fast = slow.next, fast.next.next
7+
if slow == fast:
8+
return True
9+
10+
return False

‎blind_75/src/linkedlist/lc_143_reorder_list/README.md‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
# [LC 143. Reorder List - Medium](https://leetcode.com/problems/reorder-list/)
2+
3+
4+
You are given the head of a singly linked-list. The list can be represented as:
5+
```
6+
L0 → L1 → … → Ln - 1 → Ln
7+
```
8+
9+
Reorder the list to be on the following form:
10+
```
11+
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
12+
```
13+
14+
You may not modify the values in the list's nodes. Only nodes themselves may be changed.
15+
16+
17+
18+
### Example 1
19+
20+
![Reorder List Example 1](https://assets.leetcode.com/uploads/2021/03/04/reorder1linked-list.jpg)
21+
22+
```
23+
Input: head = [1,2,3,4]
24+
Output: [1,4,2,3]
25+
```
26+
27+
### Example 2
28+
29+
![Reorder List Example 2](https://assets.leetcode.com/uploads/2021/03/09/reorder2-linked-list.jpg)
30+
31+
32+
```
33+
Input: head = [1,2,3,4,5]
34+
Output: [1,5,2,4,3]
35+
```
36+
37+
### Constraints:
38+
39+
- The number of nodes in the list is in the range [1, 5 * 10^4].
40+
- 1 <= Node.val <= 1000

‎blind_75/src/linkedlist/lc_143_reorder_list/reorder_list.py‎

Whitespace-only changes.

‎blind_75/src/linkedlist/lc_19_remove_nth_node_from_list/README.md‎

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
# [LC 19. Remove Nth Node From End of List - Medium](https://leetcode.com/problems/remove-nth-node-from-end-of-list/)
2+
3+
Given the head of a linked list, remove the nth node from the end of the list and return its head.
4+
5+
6+
### Example 1
7+
8+
![Remove Nth Node From End of List Example 1](https://assets.leetcode.com/uploads/2020/10/03/remove_ex1.jpg)
9+
10+
```
11+
Input: head = [1,2,3,4,5], n = 2
12+
Output: [1,2,3,5]
13+
```
14+
15+
### Example 2
16+
17+
```
18+
Input: head = [1], n = 1
19+
Output: []
20+
```
21+
22+
### Example 3
23+
24+
```
25+
Input: head = [1,2], n = 1
26+
Output: [1]
27+
```
28+
29+
### Constraints:
30+
31+
- The number of nodes in the list is sz.
32+
- 1 <= sz <= 30
33+
- 0 <= Node.val <= 100
34+
- 1 <= n <= sz

‎blind_75/src/linkedlist/lc_19_remove_nth_node_from_list/remove_nth_node_from_list.py‎

Whitespace-only changes.

‎blind_75/src/linkedlist/lc_206_reverse_linkedlist/README.md‎

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
# [LC 206. Reverse Linked List - Easy](https://leetcode.com/problems/reverse-linked-list/)
2+
3+
Given the head of a singly linked list, reverse the list, and return the reversed list.
4+
5+
### Example 1
6+
7+
![Reverse Linked List Example 1](https://assets.leetcode.com/uploads/2020/12/20/ex1.jpg)
8+
9+
```
10+
Input: head = [1,2,3,4,5]
11+
Output: [5,4,3,2,1]
12+
```
13+
14+
### Example 2
15+
16+
![Reverse Linked List Example 2](https://assets.leetcode.com/uploads/2020/12/20/ex2.jpg)
17+
18+
```
19+
Input: head = [1,2]
20+
Output: [2,1]
21+
```
22+
23+
### Example 3
24+
25+
```
26+
Input: head = []
27+
Output: []
28+
```
29+
30+
### Constraints:
31+
32+
- The number of nodes in the list is the range [0, 5000].
33+
- -5000 <= Node.val <= 5000

‎blind_75/src/linkedlist/lc_206_reverse_linkedlist/reverse_linkedlist.py‎

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
def reverse_list(head):
2+
prev, curr = None, head
3+
while curr:
4+
next_node = curr.next
5+
curr.next = prev
6+
prev, curr = curr, next_node
7+
8+
return prev

0 commit comments

Comments
 (0)