Sort a ordered linkedlist

A singly LL is given such that there is alternate ordering between the elements.

Ex: 1->2->13->14->11->5->4->null

Give an efficient O(n) algo to sort such a LL. There can be multiple such orderings in the given LL.

Palindrome in LinkedList

Given a linked list with node as given below:

struct node
{
char info;
struct node *next;
}

Give an O(n) algorithm to find if its a palindrome or not? You can not use more than O(1) space.

Two pointers to explore the list, reach the mid-point reverse the first half and compare the two halves

a different doubly linked list

A doubly linked list is defined as follows:
one link points to next neighbor and other link to any random node in the list.
How will you generate clone , given a linked list which follows above definition?
The list can be traversed only once.

Merge point in two linked lists

Given two link list, find out do they merge ? if yes, find the merge point. What will you do if the link list have loop at the end ? What if the lists connect at an oval like shown below?

Linked List

Find whether a circle exists in a Linked List. If yes then find the node where the circle begins. Can be done in O(n) time.

Linked List Intersection

Suppose you have 2 Singly Linked List that intersect at a Node.
Find that node in O(n) time complexity and O(1) space.