## Split Linked List in Parts Leetcode Solution

Problem Statement: Split Linked List in Parts Leetcode Solution – Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts. The length of each part should be as equal as possible: no two elements should have a size …

## Insert into a Sorted Circular Linked List LeetCode Solution

Problem Statement: Insert into a Sorted Circular Linked List LeetCode Solution – says that Given a Circular Linked List node, which is sorted in ascending 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 …

## Flatten Binary Tree to Linked List LeetCode Solution

Flatten Binary Tree to Linked List LeetCode Solution says that – Given the root of a binary tree, flatten the tree into a “linked list”:

• The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.
• The “linked list” should be in the same order as a pre-order traversal of the binary tree.

Example 1:

Input:

root = [1,2,5,3,4,null,6]

Output:

[1,null,2,null,3,null,4,null,5,null,6]

Example 2:

Input:

root = []

Output:

[]

Example 3:

Input:

root = [0]

Output:

[0]

ALGORITHM –

IDEA –

• In order to flatten a binary tree, we will first find the rightmost element of the left subtree and after we got the rightmost element we will link the right-pointer of that node with a right subtree of a given tree.
• In step 2 we will link the right pointer of the root node with the left-subtree and set the left-subtree as null.
• In step 3 now our root node is a right-subtree node same process will happen with this node and the process will still continue until all the left parts become null.

Approach for Flatten Binary Tree to Linked List Leetcode Solution –

– At first, i will run a loop i.e. while(root != null) then will take two variables and store the left-subtree.

– then will check check for the rightmost node of left-subtree by using while(k.left != null) and will link that node with right subtree using (k.right = root.right).

– then link  right pointer of root node with left subtree(root.right = left) and set left pointer of root node as null(root.left=null) and will update by ( root = root.right ) so now root is right subtree node.

– this process will continue until all left-subtree parts become right subtree. Hence, the binary tree will get flattened.

## Python Solution:

class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
while(root):

if root.left:

k = root.left
temp = root.left

while(k.right):
k = k.right

k.right = root.right

root.right = temp

root.left = None

root = root.right

## Java Solution:

class Solution {
public void flatten(TreeNode root) {
while (root != null) {
if (root.left != null) {
TreeNode k = root.left;
TreeNode temp = root.left;
while (k.right != null) k = k.right;
k.right = root.right;
root.right = temp;
root.left = null;
}
root = root.right;
}
}
}

Time complexity: O(N)

Space Complexity: O(1)

As we have traversed only once, time complexity will be o(n).

and as we haven’t taken any extra space, space complexity will be o(1) constant extra space.

## Odd Even Linked List Leetcode Solution

Problem Statement The Odd-Even Linked List LeetCode Solution – “Odd-Even Linked List” states that given a non-empty singly linked list. We need to group all nodes with odd indices together followed by the nodes with even indices, and return the reordered list. Note that the relative order inside both the …

## Add Two Numbers II Leetcode Solution

Problem Statement The Add Two Numbers II LeetCode Solution – “Add Two Numbers II” states that two non-empty linked lists represent two non-negative integers where the most significant digit comes first and each node contains exactly one digit. We need to add the two numbers and return the sum as …

## LRU Cache Leetcode Solution

Problem Statement The LRU Cache LeetCode Solution – “LRU Cache” asks you to design a data structure that follows Least Recently Used (LRU) Cache We need to implement LRUCache class that has the following functions: LRUCache(int capacity): Initializes the LRU cache with positive size capacity. int get(int key): Return the value …

## Merge k Sorted Lists Leetcode Solution

Problem Statement The Merge k Sorted Lists LeetCode Solution – “Merge k Sorted Lists” states that given the array of k linked lists, where each linked list has its values sorted in ascending order. We need to merge all the k-linked lists into one single linked list and return the …

## Populating Next Right Pointers in Each Node Leetcode Solution

Problem Statement The Populating Next Right Pointers in Each Node LeetCode Solution – “Populating Next Right Pointers in Each Node” states that given the root of the perfect binary tree and we need to populate each next pointer of the node to its next right node. If there is no next …

## Remove Nth Node From End of List Leetcode Solution

Problem Statement The Remove Nth Node From End of List Leetcode Solution – states that you are given the head of a linked list and you need to remove the nth node from the end of this list. After deleting this node, return the head of the modified list. Example: Input: …

## Remove Linked List Elements Leetcode Solution

Problem Statement In this problem, we are given a linked list with its nodes having integer values. We need to delete some nodes from the list which have value equal to val. The problem does not require to be solved in-place but we will discuss one such approach. Example List = …

Translate »