Solution for singly-circularly-linked problem

I promised to post a solution for the problem I set earlier. Now it’s time to keep the promise.

The solution is really simple because the problem itself is trivial I would say. Imagine two racers at the running track that has circular shape both starting from the same position. Let’s assume that one trained harder and can run at double speed of the another racer. Let’s imagine that they start to race but do not finish after running a one lap. They continue to race, what will happen eventually? The answer is that faster one will lap the slower runner. That’s main idea behind the solution… 🙂

Let’s translate it to a terms used in programming. You have two variables (runners) pointing at the first element of the list. Now, each time one pointer moves two elements further but other one moves only by one element from the list further. You can observe the process at this picture:

Picture showing two pointer moving along the list

Now we have two cases:

  1. If list is not circularly-linked faster runner (pointer) will reach its end and that will be a sign for us that we have detected list that is not circularly-linked
  2. If list has a cycle faster runner (pointer) will lap the slower one at some point and that will be an information for the algorithm that circularly-linked list has been detected

Obviously, the algorithm uses constant memory (two pointers). I’ll leave as an exercise to show that number of pointer shifts is not great than 2n where n is number of elements in the list.

Here you have simple implementation of this algorithm:

public class DetectCycle {

	static int steps = 0;
	
	public static void main(String[] args) {
		System.out.println(detectCycle(createLinkedList(50, -1)));
		System.out.println(steps);
	}
	
	static private boolean detectCycle(ListItem head) {
		ListItem slowerRunner = head;
		ListItem fasterRunner = head;
		steps = 0;
		while (true) {
			if (fasterRunner.getNext() == null) return false;
			fasterRunner = fasterRunner.getNext();
			if (fasterRunner.equals(slowerRunner)) return true;
			
			if (fasterRunner.getNext() == null) return false;
			fasterRunner = fasterRunner.getNext();
			if (fasterRunner.equals(slowerRunner)) return true;
			
			slowerRunner = slowerRunner.getNext();
			steps = steps + 2;
		}
	}
	
	static private ListItem createLinkedList(int numberOfItems, 
                                                 int closeCycleAtPosition) {
		ListItem head = new ListItem();
		ListItem tail = head;
		
		for (int i = 1; i <= numberOfItems; i++) {
			tail.setNext(new ListItem());
			tail = tail.getNext();
		}
		
		if (closeCycleAtPosition >= 0) {
			ListItem item = head;
			for (int i = 1; i < closeCycleAtPosition; i++)
				item = item.getNext();
			tail.setNext(item); //closing cycle at specified position
		}
		
		return head;
	}

}

and ListItem class:

public class ListItem {
	private ListItem next;
	
	public ListItem() {
		next = null;
	}
	
	public ListItem getNext() {
		return next;
	}
	
	void setNext(ListItem next) {
		this.next = next;
	}
}

EDIT: I thought that it would be nice to tell you similar riddle. Here it goes:
How to count number of elements (legnth) of the list despite it has cycle or not. Rules are the same: algorithm must be linear and use constant amount of memory. Again solution is simple!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: