Given a Sorted Singly Linked List Array, Convert it into a Balanced Binary search Tree.

Given a Sorted Array, Convert it into its Balanced Binary search TreeObjective: You have been given a sorted singly List, you need to convert it into balanced binary search tree.

Why balanced binary tree is important:

You can also create the first node as root and insert all other nodes to the right of the tree because List is in increasing order but this constructed tree won’t be a balanced tree, it will be the skewed tree and to perform operations on this tree will be O(n), not O(logn).

Input: An sorted Singly Linked List

Output: Balanced Binary Tree

Example:

Approach:

Convert a Sorted Doubly Linked List to Balanced BST.

Objective: Given a sorted doubly linked list, convert it into Balanced binary search tree

Example:

Approach:

In a Binary Tree, Create Linked Lists of all the nodes at each depth.

Objective: Given a Binary tree create Linked Lists of all the nodes at each depth , say if the tree has height k then create k linked lists.

NOTE : This problem is very similar “Print binary tree, each level in one line

Input: A binary tree

Output: K linked lists if the height of tree is k. Each linked list will have all the nodes of each level.

Example:

Add two numbers represented by a linked list, Numbers are Stored in FORWARD order

This post is the extension of   – Two numbers represented by a linked list, Number Stored in REVERSE order

Objective: Two numbers represented by a linked listwhere each node contains single digit. The digits are stored in Forward order, means head is pointing to the last digit of the number.

Input: Two numbers represented by Linked Lists

Example:

```First Number : 1007
Second Number : 93
```

Add two numbers represented by a linked list, Numbers are Stored in REVERSE order

We have similar post – Two numbers represented by a linked list, Number Stored in FORWARD order

Objective: Two numbers represented by a linked list where each node contains single digit. The digits are stored in REVERSE order, means head is pointing to the first digit of the number.

Input: Two numbers represented by Linked Lists

Example:

```First Number in REVERSE order: 5957
Second Number in REVERSE order : 59
Addition in REVERSE order : 0967
Actual Result in FORWARD ORDER : 9670```

Approach:

Reverse a Linked List – Part 2

This post is the extension of our earlier post Reverse a linked list. Here We have provided the better recursive solution in which we start reversing the list from the end.

Objective: Reverse the given linked list.

Example:

```Original List :->10->8->6->4->2
Reversed List :->2->4->6->8->10```

Approach:

Recursion:

Swap Every Kth Node in a LinkedList

Objective: Given a linked list, swap every kth node in that. If at the end of the list remaining nodes are less than k, leave them untouched.

Input: A linked list, A number k.

Example:

```Input : ->1->2->3->4->5->6->7->8->9->10 , K = 4
Output: ->4->2->3->1->8->6->7->5->9->10
```

Approach:

Objective: Write a program to Delete a Node in the Middle of a linked list, Given only access to that Node

Example:

```Original List : ->1->2->8->3->7->0->4
After Deleting the mid node (say 7) : ->1->2->8->3->0->4
```

Output: Linked list with deleted node

Approach:

• Approach is tricky and simple
• Copy the value of next node to the node which you want to delete
• Delete the next node

Find the n’th Node from the end of a given Linked List

Objective: Given a linked list and integer ‘n’, write an algorithm to find the nth node from the end in the Linked List.

Example:

```Original List : ->1->2->8->3->7->0->4
Output : 3rd Element from the end is : 7
```

Input: An unsorted linked list and integer k

Output: The kth to Last Element of a Singly Linked List

Approach:

Recursive Approach:

Remove Duplicates from an Unsorted Linked list

Objective: Write a program to remove the duplicates from an unsorted linked list

Example:

```Input Linked List : 1->2->2->4->3->3->2
Output : 1->2->4->3
```

Output: Linked list with no duplicates.

Approach:

• Create a Hash Map
• Take two pointers, prevNode and CurrNode.
• PrevNode will point to the head of the linked list and currNode will point to the head.next.

Find Intersection Point in Two Linked List

Objective: Given Two linked lists, check whether both lists intersect each other, if yes then find the starting node of the intersection.

An intersection point means the end of one linked list is linked with some node in another linked list and it forms a Y shape.

Output: Intersection Node or point

Example:

Approach:

Find the Loop in a Linked list, find its length and Break the Loop

Objective: In a given linked list, check whether it contains the loop in it, if yes then find the Loop length and break the loop.

Loop in a linked list means the last node does not point to the null, instead it points to some node in the list.

Output: Linked list contains loop or not, if yes its length and linked list after breaking the loop.

Example:

```Input : ->10->20->30->40->50->60->30->40->50->60->30->40->50->60->30

here you can see that 30->40->50->60 are repeating ,that means it has a loop
```

Approach:

Objective: Reverse the given linked list.

Example:

```Input : ->30->25->20->15->10->5

Reversed : ->5->10->15->20->25->30```

NOTE : Click Reverse a Linked List – Part 2 to see the another implementation of this problem.

Approach:

Iterative:

Merge or Combine Two Sorted Linked Lists

Objective: Given two sorted linked lists, objective is to merge both the lists in sorted order.

Input: Two sorted linked list List a, List b.

Example:

List a :

```->2->6->18

```

Listb:

```->1->3->17->19

```

Merged List: ->1->2->3->6->17->18->19

` `

Approach:

Without Recursion:

Linked List- As the name suggests it’s a list which is linked.

• Linked List consist of Nodes

Nodes are nothing but objects of a class and each node has data and a link to the next node.

```class Node {
public int data;
public Node next;

public Node(int data) {
this.data = data;
this.next = null;
}
}
```