Wednesday, January 12, 2005

Programming Puzzle

I recently heard a great little puzzle that I thought I would share with everyone.

Given a pointer to the head of a link list write a function that returns 0 if the link list ends in NULL or 1 if it is a circular link list. Note that a final node in a circular link list doesn't necessarily point to the first node, but could point to any node in the list.

Part 1) Make the function solve in O(n*n)
Part 2) Make the function solve in O(n)

I was able to solve part one without any trouble, but wasn't able to figure out part two until given a hint (use two pointers). And really it is one of those Aaha! moments so it isn't really fair as a test question, but still a example of how algorithms are fun.

1 comment:

prakash said...

use 2 pointer
one will move one node at a time
2nd will move 2 node at a time.
compare first and 2nd pointer are same..
if it is circular linked list it will be same at one point.return 0
otherwise it is not a circular linked list

Popular Posts