You are given the head of a singly linked-list. The list can be represented as:
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
You may not modify the values in the list’s nodes. Only nodes themselves may be changed.
Example 1:
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example 2:
Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Constraints:
The number of nodes in the list is in the range [1, 5 * 104].
1 <= Node.val <= 1000
https://leetcode.com/problems/reorder-list/description/
class ListNode:
# Definition for singly-linked list.
# class ListNode(object):
# def \_\_init\_\_(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def reorderList(self, head):
"""
:type head: ListNode
:rtype: None Do not return anything, modify head in-place instead.
"""
# One Pass Recursion
def rec(head, runner):
if not runner.next:
return head
nx_head = rec(head, runner.next)
# Runner will be none when any of the next two cases are met.
# nx_head.next will be none if nodes are odd numbered
# runner will be equal to nx_head when nodes are equal numbered.
# The logic works as follows
# 1,2,3,4
# 1 -> 4 -> 2 (runner = 3, nx_head = 1) (Set runner.next = None, ie. 3->None)
# 1 -> 4 -> 2 -> 3 -> None (runner = 2, nx_head = 2 << runner = nx_head, runner.next = None)
# Odd, 1,2,3
# 1 -> 3 -> 2 (runner = 2, nx_head = 2) (set runner.next = None)
# 1 -> 3 -> 2 -> None (runner = 1, nx_head = 2, << nx_head.next == None )
if not nx_head or not nx_head.next or nx_head == runner:
return None
# Save these 2 temp variables
nxt_node = runner.next
nx_nx_head = nx_head.next
nx_head.next = nxt_node
runner.next = None # we do not need it anymore, this is to have a clean ending list, otherwise cycles
nx_head.next.next = nx_nx_head
return nx_nx_head
rec(head, head)Interleave using splitting list in middle
~~~
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
“””
Do not return anything, modify head in-place instead.
“””
# Other way, reach center, reverse the list, interleave join them
# reach center
fast, slow = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# Slow is at the center now
#Reverse from slow onwards
prev = None
cur = slow
while cur:
cur.next, cur, prev = prev, cur.next, cur
# prev is the head of the reversed list now interleave join them
second = prev
first = head
while second.next:
first.next, second.next, first, second = second, first.next, first.next, second.next ~~~O(n), space O(1)
- Insert into a Sorted Circular Linked List
Medium
Companies: Facebook 2024
Given a Circular Linked List node, which is sorted in non-descending order, write a function to insert a value insertVal into the list such that it remains a sorted circular list. The given node can be a reference to any single node in the list and may not necessarily be the smallest value in the circular list.
If there are multiple suitable places for insertion, you may choose any place to insert the new value. After the insertion, the circular list should remain sorted.
If the list is empty (i.e., the given node is null), you should create a new single circular list and return the reference to that single node. Otherwise, you should return the originally given node.
Example 1:
Input: head = [3,4,1], insertVal = 2
Output: [3,4,1,2]
Explanation: In the figure above, there is a sorted circular list of three elements. You are given a reference to the node with value 3, and we need to insert 2 into the list. The new node should be inserted between node 1 and node 3. After the insertion, the list should look like this, and we should still return node 3.
Example 2:
Input: head = [], insertVal = 1
Output: [1]
Explanation: The list is empty (given head is null). We create a new single circular list and return the reference to that single node.
Example 3:
Input: head = [1], insertVal = 0
Output: [1,0]
Constraints:
The number of nodes in the list is in the range [0, 5 * 104]. -106 <= Node.val, insertVal <= 106
10-15 mins
https://leetcode.com/problems/insert-into-a-sorted-circular-linked-list/description/
Definition for a Node.
We handle the following cases:
1. The insertVal lies between 2 nodes
2. We reach the inflection point (eg. reaching 3 in 312) and the insertVal is either greater/eq than current (true tail) or smaller/eq than the next (true head)
If we do not hit either of these cases before we have reached starting point, then the list has all same elements, in which case we can insert anywhere.
"""
class Node:
def \_\_init\_\_(self, val=None, next=None):
self.val = val
self.next = next
"""
class Solution:
def insert(self, head: 'Optional[Node]', insertVal: int) -> 'Node':
if not head:
ret = Node(insertVal)
ret.next = ret
return ret
cur = head
insertNode = Node(insertVal)
while cur.next!=head:
if cur.val <= insertVal <= cur.next.val:
break
if cur.val > cur.next.val and (insertVal <= cur.next.val or insertVal >= cur.val):
break
cur = cur.next
cur.next, insertNode.next = insertNode, cur.next
return headO(n), O(1) space
- Diameter of Binary Tree
Solved
Easy
Topics
Companies Facebook
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.
The length of a path between two nodes is represented by the number of edges between them.
Example 1:
Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].
Example 2:
Input: root = [1,2]
Output: 1
Constraints:
The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100
https://leetcode.com/problems/diameter-of-binary-tree/description/
class TreeNode:
Definition for a binary tree node.
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def diameterRec(node):
if not node:
return 0,0
if not node.left and not node.right:
return 1,0
left_depth, ldiameter = diameterRec(node.left)
right_depth, rdiameter = diameterRec(node.right)
cur_diameter = left_depth + right_depth
maxDepth = max(left_depth, right_depth) + 1
maxDiameter = max(cur_diameter, ldiameter, rdiameter)
return maxDepth, maxDiameter
_, maxDiameter = diameterRec(root)
return maxDiameterO(n), O(1) Space
- Binary Tree Right Side View
Solved
Medium
Topics
Companies Facebook
Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
Example 1:
Input: root = [1,2,3,null,5,null,4]
Output: [1,3,4]
Example 2:
Input: root = [1,null,3]
Output: [1,3]
Example 3:
Input: root = []
Output: []
Constraints:
The number of nodes in the tree is in the range [0, 100].
-100 <= Node.val <= 100
https://leetcode.com/problems/binary-tree-right-side-view/description/
Definition for a binary tree node.
from collections import deque
# Definition for a binary tree node.
# class TreeNode(object):
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution(object):
def rightSideView(self, root):
"""
:type root: TreeNode
:rtype: List[int]
"""
if not root:
return []
q = deque()
ret = []
q.append(root)
while q:
ret.append(q[0].val)
for i in range(len(q)):
node = q.popleft()
if node.right:
q.append(node.right)
if node.left:
q.append(node.left)
return retO(n), O(n)
- Find K Closest Elements
Solved
Medium
Topics
Companies
Given a sorted integer array arr, two integers k and x, return the k closest integers to x in the array. The result should also be sorted in ascending order.
An integer a is closer to x than an integer b if:
|a - x| < |b - x|, or
|a - x| == |b - x| and a < b
Example 1:
Input: arr = [1,2,3,4,5], k = 4, x = 3
Output: [1,2,3,4]
Example 2:
Input: arr = [1,1,2,3,4,5], k = 4, x = -1
Output: [1,1,2,3]
Constraints:
1 <= k <= arr.length
1 <= arr.length <= 104
arr is sorted in ascending order.
-104 <= arr[i], x <= 104
https://leetcode.com/problems/find-k-closest-elements/
import bisect
class Solution:
def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:
if k == len(arr):
return arr
if x <= arr[0]:
return arr[:k]
elif x >= arr[-1]:
return arr[-k:]
insert_idx = bisect.bisect_left(arr, x)
l = insert_idx - 1
r = insert_idx
while r-l-1 < k:
if l < 0:
r+=1
continue
if r == len(arr) or abs(x-arr[l]) <= abs(x-arr[r]):
l-=1
else:
r+=1
return arr[l+1:r]O(log(n) + k), O(1)
- Find Leaves of Binary Tree
Medium
Given the root of a binary tree, collect a tree’s nodes as if you were doing this:
Collect all the leaf nodes.
Remove all the leaf nodes.
Repeat until the tree is empty.
Example 1:
Input: root = [1,2,3,4,5]
Output: [[4,5,3],[2],[1]]
Explanation:
[[3,5,4],[2],[1]] and [[3,4,5],[2],[1]] are also considered correct answers since per each level it does not matter the order on which elements are returned.
Example 2:
Input: root = [1]
Output: [[1]]
Constraints:
The number of nodes in the tree is in the range [1, 100].
-100 <= Node.val <= 100
https://leetcode.com/problems/find-leaves-of-binary-tree/
from collections import defaultdict
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findLeaves(self, root: Optional[TreeNode]) -> List[List[int]]:
leaf = defaultdict(list)
def rec(node):
nonlocal leaf
if not node:
return -1
val_l = rec(node.left)
val_r = rec(node.right)
valthis = max(val_l, val_r) + 1
leaf[valthis].append(node.val)
return valthis
rec(root)
return leaf.values()O(n) time O(n) space
-
Array Hashing43
-
Two Pointers12
-
Sliding Window6
-
Linked List13
-
Stacks/Queues16
-
Backtracking15
-
Binary Search / Div Conq.13
-
Trees (binary/bst)27
-
Heaps / Priority Queue12
-
Dynamic Programming 1D4
-
Prefix/Postfix6
-
Trie3
-
Graphs25
-
Dynamic Programming22
-
DFS/BFS2
-
2D Geometry Etc.4
-
Math3
-
Hash Map1
-
Mock Interview6
