Sort Linked List using Merge Sort.
Given a Linked list, Sort it using Merge Sort Algorithm.
Merge sort is preferred algorithm for sorting a linked list, lets see why,
The way linked list is structured which doesn't allow random access makes some other algorithms like Quicksort perform poorly, So Merge sort is often preferred algorithm for sorting linked list.
Lets understand what is the input and the expected output.
Tower Of Hanoi
Lets understand what is the input and the expected output.
So the question is, You have given a 3 Peg (Start peg, Auxiliary/helper peg and End Peg)
Start peg contains 3 disks of different sizes as shown. You have to move all the disk from Start peg to End peg using Auxiliary peg.
There are few rules that need to keep in mind,
1. Only one disk can be moved at a time.
2. Large size disk can't be placed on top of small sized disk.
Reverse a Linked list
Lets understand what is the input and the expected output.
Detect loop in Linked list.
Identify start node of loop in Linked list.
Remove loop in Linked list.
What is Loop in Linked list?
Generally, the last node of the linked list points to NULL, which is a indication of end of list.
But in Linked list containing Loop, last node instead of pointing NULL, it points to some of the internal node/starting node/itself.
In this case, If we traverse the Linked list node one by one, our traversal will never ends as it goes in loop.
Check below images for better understanding on how Linked list containing loop looks like.
Find diameter of Binary Tree.
What is Diameter of a Binary Tree?
A longest path or route between any two nodes in a tree is called as Diameter/Width of binary tree.
The diameter of tree may or may not pass through the root.
The diagram below shows two trees each with diameter 7, diameter are shaded with blue nodes.
Diameter of node = height of Left sub tree of node + height of Right sub tree of node + 1 (node itself).
