Monday, November 17, 2008

Problems on Linked lists

1. Midpoint of a linked list

Given pointer to the head of a linked list, find the middle element in single traversal (single loop).

2. Cycle in a linked list

Given pointer to the head of a linked list, find whether there is a cycle in the list in O(n). For e.g. if in a list the last element->next pointer points to one of the elements in between, there there is no end to the list and a cycle exist.

3. Point of intersection of 2 linked lists

Given pointers to the heads of two linked lists. They intersect at some element, and proceed as a single list there-onwards. Find the point of intersection in O(n). For visualization purpose, consider the linked lists forming a shape 'Y'.

4. 'n'th element from the end in a linked list

Given pointer to the head of a linked list, find the 'n'th element from the end in the list in single traversal.

No comments: