SDE - 1

1. If the size of the linked list is 1 then return the head
2. Find mid using The Tortoise and The Hare Approach
3. Store the next of mid in head2 i.e. the right sub-linked list.
4. Now Make the next midpoint null.
5. Recursively call mergeSort() on both left and right sub-linked list and store the new head of the left and right linked list.
6. Call merge() given the arguments new heads of left and right sub-linked lists and store the final head returned after merging.
7. Return the final head of the merged linkedlist.

1) Create an empty stack and push -1 to it. 
The first element of the stack is used 
to provide a base for the next valid string. 

2) Initialize result as 0.

3) If the character is '(' i.e. str[i] == '('), 
push index'i' to the stack. 

2) Else (if the character is ')')
a) Pop an item from the stack (Most of the 
time an opening bracket)
b) If the stack is not empty, then find the
length of current valid substring by taking 
the difference between the current index and
top of the stack. If current length is more 
than the result, then update the result.
c) If the stack is empty, push the current index
as a base for the next valid substring.

3) Return result.