Flatten a linked list

Given a linked list which can grow in both horizontal and vertical directions (right and down), flatten it into a sorted singly linked list provided that each horizontal and vertical list is already sorted.

Construct a Cartesian Tree from In-order Traversal

Write an efficient algorithm to construct a Cartesian tree from in-order traversal. A Cartesian tree is a binary tree with the heap property: the parent of any node has smaller value than the node itself.

Check if a linked list of strings is palindromic

Given a linked list of strings, check whether concatenation of all values in the list together forms a palindrome. It is not permissible to construct a string out of the linked list nodes and check that string for palindrome.

Recursive solution to sort a stack

Given a stack, sort it using recursion. The use of any other data structures (like containers in STL or Collections in Java) is not allowed.

Flatten a multilevel linked list

Given a list which can grow in both horizontal and vertical directions (right and down), flatten it into a singly linked list. The conversion should be in such a way that down node is processed before the next node for any node.