Good questions in Linked List

1. Given a linked list of 0s, 1s and 2s, sort it.
2. Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Order of elments in output lists doesn’t matter.
3. Given a Doubly Linked List which has data members sorted in ascending order. Construct a Balanced Binary Search Tree which has same data members as the given Doubly Linked List. The tree must be constructed in-place (No new node should be allocated for tree conversion)
4. Given a Singly Linked List, write a function to delete a given node. Your function must follow following constraints:

               a) It must accept pointer to the start node as first parameter and node to     be  deleted as second parameter i.e., pointer to head node is not global.

               b) It should not return pointer to the head node.

               c) It should not accept pointer to pointer to head node.

5. Write a function detectAndRemoveLoop() that checks whether a given Linked List contains loop and if loop is present then removes the loop and returns true.

6. Given a Linked List of integers, write a function to modify the linked list such that all even numbers appear before all the odd numbers in the modified linked list.

7. Given a linked list, write a function to reverse every alternate k nodes (where k is an input to the function) in an efficient way. Give the complexity of your algorithm.

Example:
Inputs:   1->2->3->4->5->6->7->8->9->NULL and k = 3
Output:   3->2->1->4->5->6->9->8->7->NULL.

8. Give a linked list, sort the list using merge sort

9. Write a function AlternatingSplit() that takes one list and divides up its nodes to make two smaller lists ‘a’ and ‘b’. The sublists should be made from alternating elements in the original list. So if the original list is 0->1->0->1->0->1 then one sublist should be 0->0->0 and the other should be 1->1->1
10. Given a singly linked list, write a function to swap elements pairwise. For example, if the linked list is 1->2->3->4->5 then the function should change it to 2->1->4->3->5, and if the linked list is 1->2->3->4->5->6 then the function should change it to 2->1->4->3->6->5.
11. Write a recursive function to print reverse of a Linked List
12. Write a recursive function treeToList(Node root) that takes an ordered binary tree and rearranges the internal pointers to make a circular doubly linked list out of the tree nodes. The”previous” pointers should be stored in the “small” field and the “next” pointers should be stored in the “large” field. The list should be arranged so that the nodes are in increasing order. Return the head pointer to the new list
13. Given only a pointer to a node to be deleted in a singly linked list, how do you delete it?
14. Nth node from the end of a Linked List
15. Pairwise swap elements of a given linked list

16. You have given a linked list in which each node have three items, 1) data, 2) a next pointer and 3) a random pointer which is pointing to its successor in sorted order. Replicate it  / create a copy of this linked list ? (Need to generate a new linked list in O(n) + O(n) complexity).